Рефераты | Рефераты по информатике, программированию | Разработка методов исследования характеристик генетического алгоритма распределе- Разработка методов исследования характеристик генетического алгоритма распределе-ния цепей по слоям в МСМ Категория реферата: Рефераты по информатике, программированию Теги реферата: реферат экологические проблемы, найти реферат Добавил(а) на сайт: Balashov. Предыдущая страница реферата | 1  2  3 Слой 2:  4 10 Слой 3:  12 13 14 15 Слой 4:  3 5 Слой 1,2:  0 3 5 6 9

Из этого примера видно, что в потомках цепи располагаются только в четырех слоях, тогда как в каждом родителе используется, пять слоев. Таким образом, потомки имеют высшее значение оценочной функции, чем родители. Если продолжить этот процесс, то можно прийти к оптимальному решению.

Операция мутации применяется к одной хромосоме и незначительно преобразует ее путем локальных случайных перемещений. Однако применение различных операторов мутации убыстряет или замедляет нахождение приемлемого решения задачи. Неплохие результаты дает применение оператора мутации известного в литературе как “Золотое сечение”.

При реализации алгоритма были реализованы также операторы транслокации (перенос части одной хромосомы на другую, если обнаруживается недостаток одних и избыток других участков хромосом, то избыточные заменяются на недостающие случайным образом), оператор сегрегации (организован как чисто случайный выбор генов из всей популяции, пока не “соберется” хромосома) и операторы инверсии (двухточечные с инверсией между локальными точками и инверсия частей хромосомы попавших за локальные точки).

Но, как выяснилось в ходе исследования, ощутимого вклада в решение задачи они не внесли. Цель их, как и операторов мутации, – предотвращение единообразия во множестве решений. Сознательное ухудшение некоторых решений привносит новую информацию и является механизмом выхода из “локальных” ям.

Попытка реализации искусственного (принудительного) выхода из “локальных” ям не привнесла улучшения или убыстрения нахождения приемлемого решения. Реализован выход следующим образом. При обнаружении, что более половины новой популяции состоит из одинаковых решений происходит уничтожение популяции, а новая создается случайным образом и в нее добавляется лучшее решение полученное алгоритмом. Эта попытка подтверждает что алгоритм в ходе решения задачи накапливает информацию и является адаптивной системой.

Таким образом получается новая популяция, которая в свою очередь подвергается действию генетиеских операторов. Следует отметить ,что необязательно применять генетические операторы к каждой хромосоме лучшее решение может переносится в новую популяцию без изменения (принцип эллитизма).

Рассмотренный процесс выполняется итерационно до тех пор, пока не будет получено приемлемое решение.

По выше описанному алгоритму была сделана программа на языке Borland C++ под Windows 95, которая позволяет эффективно использовать все богатство генетического инструментария.

Поделитесь этой записью или добавьте в закладки