алгоритъм на мравките

Биониката използва методи, открити в растителния/животинския свят, при проектирането на нови системи. Пример за това е житно стъбло и конструкция на мост. Подобно приложение на биониката е алгоритъм на мравките: ACO - Ant Clony Optimization.

Мравките са обществени насекоми със силно изразен полиморфизъм - съществуват различни форми (в рамките на същия вид), изпълняващи различни функции (царица, войници, работнички, чистачки).

Социалният им живот е сложен и е свързан с различни форми на комуникация. Особена форма е химическата - чрез феромони.

Ролята на мравките работнички е да събират храна. Те първоначално се движат по случаен/хаотичен начин и при откриване на източник на храна се завръщат към колонията си, като по целия обратен път полагат следи от феромон. Той служи за комуникация с останалите мравки. Ако други мравки се натъкнат на маршрута на първата мравка, те с голяма степен на вероятност престават да се движат по случаен начин и поемат по оставената следа от феромон до източника. В случай, че също открият храна, при връщането си оставят собствена следа от феромон върху вече съществуващата. Така количеството феромон се увеличава и маршрута до източника на храна става още по-привлекателен за следващите мравки.

Феромонът има свойството да се изпарява с времето - това от своя страна снижава способността му да привлича други мравки. Процентът изпарен феромон е правопропорционален на времето за преминаване разстоянието до източника на храната и обратно. Така, интензитетът на останалия феромон остава по-висок при по-кратък път между същите две крайни точки. В разглеждания случай процесът на изпаряването на феромона представлява предимство, тъй като се избягва решение, представляващо локален оптимум. Ако, в алгоритъма на мравките, не съществуваше ефектът с изпарението, то пътя избран от първата мравка ще бъде твърде привлекателен за всички следващи, което на свой ред би ограничило значително изследваната от "мравките" област за търсене на решение.

Да се реализира проект на тема алгоритъм на мравките, представляващ междупредметни връзки между Биология и Информатика.

Реализираният проект да представя постепенно оформяне на най-късия път между две предварително избрани точки, използвайки алгоритъм на мравките. Във всеки отделен момент проектът генерира "нова мравка със собствен маршрут", като последователно се премахва по-голямото получено отклонение от оптималния маршрут.

Ако в проекта движението се апроксимира с праволинейна пътека, то в реалния живот това не се случва. И една от причините са естествените прегради, затрудняващи придвижването на отделните мравки. Поведението на реалните мравки се определя не само от интензитета на оставения феромон, но и от пряката видимост до следващата точка от маршрута.

Мравките сами по себе си са елементарни агенти, но са способни да вземат адекватни решения в сложна ситуация благодарение на кооперативното си поведение.

Процесът на на кооперативно поведение на мравките се характеризира с положителна обратна връзка - вероятността, с която поредната мравка избира определен път нараства с увеличаване броя мравки избрали последно същия маршрут. Основната причина за тази положителна обратна връзка е по-голямото количество натрупан феромон по оптималния (за момента) маршрут. В случая феромона, дава възможност за неявно оценяване на решението.

При управлението на сложни системи, предложеният алгоритъм от Marco Doridgo на основа интелигентен рояк предлага алтернатива на централизацията чрез автономност и разпределена функционалност при намиране на оптимално решение. Автономността дава възможност за управление на поведението чрез отношение на видимостта (субективното) и интензивността на следата (колективното).

В реализираният проект алгоритъм на мравките интерактивното приложение осъществява следното:

генерират се двойка случайни числа, от които се формира координати на точка;

точката се визуализира на екрана

до момента процесът илюстрира хаотичното търсене;

след, програмно заложен, интервал от време точките се оцветяват по два начина: ако координатите са в рамките на успоредника свързващ горния-ляв и долния-десен край на изображението точката е в обичайния си цвят, ако не е точката се оцветява във фоновия цвят на изображението.

при по-внимателно разглеждане на графиката се отчета факта, че част от точките се вплътняват, а част от точките губят част от контура си. Чрез този подход се илюстрира основната идея заложена в алгоритъм на мравките;

процесът продължава неопределено време, след около час работа на екрана има грапаво очертан, почти запълнен успоредник и малко и много слабо представени цветни точки.

Разгледайте други примерни проекти реализиращи междупредметни връзки, за които е ползвана подобна логическа структура на графичните обекти и/или приложени сходни алгоритми. Прочетете допълнителен материал за: резус-фактор, решетка на Пънет, кръводаряване.