Кіріспе

Оптимизациялау алгоритмі

Компьютерлік ғылым мен операциялық зерттеулерде құмырсқалар колониясын оптимизациялау алгоритмі (ACO) – графиктер арқылы ең жақсы жолдарды табуға келтірілетін есептеу мәселелерін шешуге арналған ықтималдық әдіс. Жасанды құмырсқалар – нақты құмырсқалардың мінез-құлқынан шабыттанған көп агенттік әдістер. Биологиялық құмырсқалардың феромонға негізделген байланысы көбінесе қолданылатын басты парадигма болып табылады. Жасанды құмырсқалар мен жергілікті іздеу алгоритмдерінің үйлесімдері, мысалы, көлік және интернет маршрутын қамтитын көптеген оптимизациялау міндеттері үшін таңдаулы әдіс атанды. Мысалы, құмырсқалар колониясын оптимизациялау – құмырсқалар колониясының іс-әрекеттеріне негізделген оптимизациялау алгоритмдерінің класы. Жасанды "құмырсқалар" (мысалы, модельдеу агенттері) барлық мүмкін шешімдерді көрсететін параметрлік кеңістікте қозғалып, ең жақсы шешімдерді табады. Нақты құмырсқалар қоршаған ортаны зерттеу кезінде бір-бірін ресурстарға бағыттайтын феромондарды тарату арқылы байланысады. Модельделген "құмырсқалар" да өздерінің орналасқан жерін және шешімдерінің сапасын жазады, соның салдарынан кейінгі модельдеу кезеңдерінде көбірек құмырсқалар жақсы шешімдерді табады. Бұл тәсілдің бір түрі – аралар алгоритмі, ол басқа әлеуметтік жәндік – бал арасының жем іздеу үлгілеріне ұқсас. Бұл алгоритм құмырсқалар колониясы алгоритмдері отбасының мүшесі, ұсақ интеллект әдістерінің құрамында және метаэвристикалық оптимизацияны құрайды. Алғаш рет 1992 жылы Марко Дориго докторлық диссертациясында ұсынған, алғашқы алгоритм граф ішіндегі ең жақсы жолды табуға бағытталған, ол құмырсқалардың өз колониясы мен тамақ көзі арасындағы жолды іздеуіне негізделген. Бастапқы идея кейіннен сандық мәселелердің кең ауқымын шешу үшін дамытылды, нәтижесінде құмырсқалардың мінез-құлқының әртүрлі аспектілеріне сүйене отырып, бірнеше мәселелер пайда болды. Жалпы алғанда, ACO модельге негізделген іздеуді жүзеге асырады және үлестіру алгоритмдерін бағалаумен ұқсастықтарды бөліседі.

Шолу

Табиғи әлемде кейбір түрлердің құмырсқалары (бастапқыда) кездейсоқ жүріп, тамақ тапқанда фермондық іздер қалдырып, өз колониясына қайта оралады. Егер басқа құмырсқалар мұндай жолды тапса, олар енді кездейсоқ сапарға шықпайды, керісінше, сол ізді жалғастырып, қайта оралып, егер тамақ тапса, оны нығайтады (Құмырсқалардың қарым-қатынасы туралы қараңыз). Бірақ уақыт өте келе фермондық іздер буланып, оның тартымдылығы азаяды. Құмырсқаның жолмен барып-келуіне қанша уақыт кетсе, фермонның булануына соғұрлым көп уақыт жетеді. Қысқа жолға қарағанда, одан жиі өтеді, сондықтан қысқа жолдағы фермон тығыздығы ұзын жолға қарағанда жоғары болады. Фермонның булануының тағы бір артықшылығы – жергілікті жақсы шешімге тоқталып қалудан сақтану. Егер булану болмаса, алғашқы құмырсқалар таңдаған жолдар келесілері үшін тым тартымды болар еді. Бұл жағдайда шешімдерді іздеу кеңістігі шектелер еді. Нақты құмырсқа жүйелерінде фермонның булануының әсері белгісіз, бірақ жасанды жүйелерде ол өте маңызды. Соның нәтижесінде, егер бір құмырсқа қоныстан тамаққа дейінгі жақсы (яғни қысқа) жолды тапса, басқа құмырсқалар да сол жолмен жүруге бейім, ал оң кері байланыс көптеген құмырсқалардың бір жолмен жүруіне әкеледі. Құмырсқалар колониясы алгоритмінің идеясы – осы мінез-құлқыны «үлгіленген құмырсқалармен» шешуге тиіс мәселені бейнелейтін граф бойынша жүріп имитациялау болып табылады.

Ақылды объектілердің қоршаған орта желілері

Жаңа ұғымдар қажет, себебі «интеллект» енді орталықтандырылмаған, бірақ барлық ұсақ-түйек объектілерде кездеседі. Адамдарға қатысты ұғымдар деректерді өңдеу, басқару блогы мен есептеу қуаты орталықтандырылған АТ жүйелерін жасауға алып келген. Бұл орталықтандырылған бірліктер өнімділігін үнемі арттырып келеді және оларды адам миымен салыстыруға болады. Ми моделі компьютерлердің соңғы көрінісіне айналды. Ақылды объектілердің айналадағы желілері және, ерте не кеш, нанотехнологияларға негізделген, тіпті одан да тараған жаңа буын ақпараттық жүйелер бұл ұғымды түбегейлі өзгертеді. Құмырсқаға теңеуге болатын кішкентай құрылғылар өздерінен жоғары интеллектке ие бола алмайды. Шындығында, олардың интеллектын шамалы деп санауға болады. Мысалы, кез келген математикалық мәселені шеше алатын жоғары өнімді калькуляторды адам денесіне имплантацияланған биочипке немесе тауарларды қадағалауға арналған интеллектуалды таңбаға енгізу мүмкін емес. Бірақ, егер бұл объектілер бір-бірімен байланысқанда, олар құмырсқалар мен аралардың колониясына теңеуге болатын интеллект түрін пайда етеді. Кейбір мәселелерде, бұл интеллект түрі ми сияқты орталықтандырылған жүйенің ойлауынан артық болуы мүмкін. Табиғат, егер барлық ұсақ организмдер бірдей негізгі қағиданы орындаса, макроскопиялық деңгейде ұжымдық интеллектті қалай құруға болатынына көптеген мысалдар келтіреді. Әлеуметтік жәндіктердің колониялары адам қоғамынан өзгеше келетін бұл модельді жақсы көрсетеді. Бұл модель тәуелсіз бірліктердің өзара әрекеттесуіне негізделген, олардың мінез-құлқы қарапайым және болжаусыз. Олар белгілі бір міндеттерді орындау үшін айналасында қозғалады және осы үшін өте шектеулі ақпаратқа ие. Мысалы, құмырсқалар колониясы айналадағы объектілер желісіне де қолданылатын көптеген қасиеттерді көрсетеді. Құмырсқалар колониясы қоршаған ортаның өзгеруіне бейімделуге өте қабілетті, сондай-ақ, егер бір жеке тұлға белгілі бір міндетті орындай алмаса, оны шешуде өте күшті. Бұл икемділік үнемі дамып келе жатқан объектілердің мобильді желілері үшін де өте пайдалы болар еді. Компьютерден цифрлық объектіге жылжыған ақпарат бөлігі құмырсқалар сияқты әрекет етеді. Олар желі арқылы қозғалып, бір түйінен екіншісіне мүмкіндігінше жылдам жете алу мақсатымен өтеді.

Жасанды феромондық жүйе

Фермонға негізделген коммуникация – табиғатта кеңінен кездесетін ең тиімді коммуникация түрлерінің бірі. Феромонды ара, құмырсқа және термиттің сияқты әлеуметтік жәндіктер өздерінің арасындағы және топтағы байланыс үшін пайдаланады. Осы мүмкіндігінің арқасында жасанды феромондар көп роботты және роботтар тобындағы жүйелерде қолданыс тапты. Феромонға негізделген коммуникация химиялық немесе физикалық (RFID тегтері, жарық, дыбыс) жолдармен іске асырылды. Дегенмен, бұл іске асырулар табиғаттағы феромонның барлық ерекшеліктерін толық қайталай алмады. 2007 жылы Garnier, Simon және авторлар тобы IEEE жарияланымда микроавтономды роботтармен феромонға негізделген коммуникацияны зерттеу үшін проекцияланған жарықты қолдануды эксперименттік тұрғыдан ұсынды. Тағы бір зерттеу роботтардың қозғалатын көлденең LCD экраны арқылы феромонды іске асыратын жүйені ұсынды, роботтарда төмен қаратылған жарық сенсорлары арқылы олардың астындағы бейнелерді тіркеу мүмкіндігі болды.

Жалпы кеңейтулер

Міне, АКО алгоритмдерінің ең көп таралған түрлері.

Құмырсқа жүйесі (AS)

Құмырсқа жүйесі – алғашқы ACO алгоритмі. Бұл алгоритм жоғарыда сипатталған алгоритммен сәйкес келеді. Оны Дориго жасаған.

Элиталық құмырсқа жүйесі

Бұл алгоритмде, жаһандық ең жақсы шешім әрбір итерациядан кейін (бұл жол қайтадан басылмаған болса да) өзінің жолына феромонды қалдырады, сондай-ақ барлық басқа құмырсқалар да. Элиталық стратегияның мақсаты – барлық құмырсқалардың іздеуін қазіргі ең жақсы маршруттың қабырғаларын қамтитын шешім құруға бағыттау.

Максималды-минималды жүйе (MMAS)

Бұл алгоритм әрбір жолдағы феромонның максималды және минималды мөлшерін реттейді. Феромонды жолға тек жаһандық ең жақсы тур немесе итерациялық ең жақсы тур ғана қоса алады. Іздеу алгоритмінің тоқтап қалуын болдырмау үшін, әрбір жолдағы феромон мөлшерінің мүмкін диапазоны [τmax,τmin] интервалымен шектеледі. Барлық қабырғалар шешімдерді кеңірек іздеуге ынталандыру үшін τmax мәнімен бастамаланады. Іздеу тоқтап қалған кезде жолдар қайтадан τmax мәнімен бастамаланады.

Рангы бойынша құрылған құмырсқа жүйесі (ASrank)

Барлық шешімдер ұзындығы бойынша реттеледі. Осы итерацияда тек белгілі бір саны ең жақсы құмырсқаларға ғана іздерін жаңартуға рұқсат беріледі. Әрбір шешімге қалдырылатын феромон мөлшері салмақталған, яғни қысқа жолмен шешілген мәселелер ұзақ жолмен шешілгендерге қарағанда көбірек феромон қалдырады.

Параллель құмырсқалар колониясын оңтайландыру (PACO)

Қамыршалар колониясы жүйесі (ҚКС) коммуникация стратегияларымен әзірленді. Жасанды қамыршалар бірнеше топқа бөлінді. ҚКС-дегі топтар арасындағы феромон деңгейін жаңарту үшін жеті коммуникациялық әдіс ұсынылды және олар саяхатшы сатушы мәселесінде қолданылады.

Тұрақты ортогональды құмырсқалар колониясы (COAC)

Феромондық депозит механизмі құмырсқаларға шешімдерді бірлесіп, тиімді іздеуге мүмкіндік береді. Ортогональды жобалау әдісін пайдалану арқылы, қолжетімді домендегі құмырсқалар өздері таңдаған аймақтарды жылдам және тиімді зерттей алады, соның нәтижесінде жаһандық іздеу қабілеті мен дәлдігі артады. Ортогональды жобалау әдісі және радиусты бейімдеу әдісі практикалық мәселелерді шешуде кеңірек артықшылықтар беру үшін басқа оңтайландыру алгоритмдеріне де қолданылуы мүмкін.

Қайталанатын құмырсқалар колониясын оңтайландыру

Бұл тұтас іздеу саласын бірнеше кіші салаға бөліп, осы кіші салалардағы мақсатты міндетті шешетін құмырсқа жүйесінің рекурсивті түрі. Барлық кіші салалардың нәтижелері салыстырылады және олардың ең жақсылары келесі деңгейге өтеді. Таңдалған нәтижелерге сәйкес кіші салалар одан әрі бөлінеді және процесс қажетті дәлдікке қол жеткенше қайталанады. Бұл әдіс дұрыс қойылмаған геофизикалық инверсия мәселелерінде сынақтан өтті және жақсы нәтижелер көрсетті.

Ынтымақтастық

Алгоритмнің кейбір нұсқалары үшін оның конвергентті екенін дәлелдеу мүмкін (яғни, ол шекті уақытта жаһандық оптимумды табуға қабілетті). Құмырсқалар колониясы алгоритмі үшін конвергенцияның алғашқы дәлелі 2000 жылы график негізіндегі құмырсқалар жүйесі алгоритмі үшін жасалды, ал кейіннен ACS және MMAS алгоритмдері үшін де дәлелденді. Көптеген метаэвристикалар сияқты, конвергенцияның теориялық жылдамдығын бағалау өте қиын. Ұдайы құмырсқалар колониясы алгоритмінің әртүрлі параметрлеріне (қабырғаларды таңдау стратегиясы, қашықтық өлшеу метрикасы және феромонның булану деңгейі) қатысты жасалған өнімділік талдауы, оның өнімділігі мен конвергенция жылдамдығы таңдалған параметрлердің мәндеріне, әсіресе феромонның булану деңгейіне сезімтал екенін көрсетті. 2004 жылы Злочин және оның әріптестері COAC типіндегі алгоритмдерді энтропия және үлестіру алгоритмін бағалаудағы стохастикалық градиенттік төмендеудің ассимиляцияланған әдістері ретінде қарастыруға болатынын көрсетті. Олар осы метаэвристикаларды "зерттеуге негізделген модель" деп ұсынды.

Наноэлектрониканың физикалық жобалаудағы құрылғыны өлшеу проблемасы

45 нм CMOS негізіндегі сезім күшейткіш тізбегін құмырсқалар колониясының оңтайландыруы (ACO) арқылы өте қысқа мерзімде оңтайлы шешімдерге жетуге болады. Құмырсқалар колониясының оңтайландыруына негізделген кері тізбек синтезі тиімділікті едәуір арттыра алады.

Басылымдар (таңдалған)

М. Дориго, 1992 жыл. Оптимизация, оқыту және табиғи алгоритмдер, докторлық диссертация, Милан политехникасы, Италия. М. Дориго, В. Маниеццо және А. Колорни, 1996. "Құмырзалар жүйесі: Ынтымақтасқан агенттер колониясының оңтайландыруы", IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26 (1): 29–41. М. Дориго және Л. М. Гамбардела, 1997. "Құмырзалар колониясы: Саяхатшының мәселесіне кооперативтік оқыту тәсілі". Эволюциялық есептеулер жөніндегі IEEE транзакциялары, 1 (1): 53–66. М. Дориго, Г. Ди Каро және Л. М. Гамбардела, 1999. "Дискретті оңтайландыру үшін құмырзалар алгоритмдері". Жасанды өмір, 5 (2): 137–172. Е. Бонабо, М. Дориго және Г. Тераулаз, 1999. Шұбыршық интеллект: Табиғи жүйелерден жасанды жүйелерге дейін, Оксфорд университетінің баспасы. М. Дориго және Т. Штуцле, 2004. Құмырзалар колониясын оңтайландыру, MIT Press. М. Дориго, 2007. "Құмырзалар колониясын оңтайландыру". Scholarpedia. К. Блум, 2005. "Құмырзалар колониясын оңтайландыру: Кіріспе және соңғы трендтер". Өмір физикасының шолулары, 2: 353–373. М. Дориго, М. Бираттари және Т. Штуцле, 2006. Ant Colony Optimization: Жасанды құмырзалар – есептеу интеллектісінің техникасы. TR/IRIDIA/2006 023. Мохд Муртада Мохамад, "Артикуляциялық роботтардың қозғалысын жоспарлауда жем іздеу стратегиясын қолдану", "Жасанды интеллект бойынша ақпараттық технологияның арнайы мәселелері" журналы, 20 том, 4 нөмір, 163–181 беттер, 2008 жылғы желтоқсан, Н. Монмарше, Ф. Гинан және П. Сиарри (ред.), "Жасанды құмырзалар", 2010 жылғы тамыз, қатты мұқабасы, 576 бет. А. Кажаров, В. Курейчик, 2010. "Көліктік мәселелерді шешу үшін құмырзалар колониясын оңтайландыру алгоритмдері", Journal of Computer and Systems Sciences International, 49 том, 1 нөмір, 30–43 беттер. C. M. Pintea, 2014, Комбинаторлық оңтайландыру мәселелері үшін био-шабыттандырылған есептеудегі жетістіктер, Springer. К. Салим, Н. Фисал, М. А. Бахарудин, А. А. Ахмед, С. Хафиза және С. Камила, "Сымсыз сенсорлық желілер үшін қиылысқан қабаттық архитектураға негізделген құмырзалар колониясы шабыттандырылған өзіндік оңтайландырылған маршруттау протоколы", WSEAS Trans. Commun., 9 том, 10 нөмір, 669–678 беттер, 2010 жыл. К. Салим және Н. Фисал, "Сымсыз сенсорлық желілерде өзіндік оңтайландырылған деректерді сенімді маршруттау үшін жақсартылған құмырзалар колониясы алгоритмі", Желілер (ICON) 2012, 18-ші IEEE халықаралық конференциясы, 422–427 беттер. Abolmaali S, Roodposhti FR. Портфельді оңтайландыру – құмырзалар колониясы әдісін қолдану, Тегеран қор биржасының мысалы. Есепке алу журналы, 2018 жылғы наурыз, 8(1).