Приспособленность - хромосома
Cтраница 1
Приспособленность произвольной хромосомы р определяется расстоянием по Хеммингу p ( pi, рт) между pi и рт ( числом несовпадающих компонент в этих наборах), причем f ( pi) экспоненциально уменьшается с ростом p ( pi, рт, т.е. чем больше различие между pi и рт, тем меньше ее приспособленность. Новое поколение Pt l получается из старого Р путем отбора и мутации последовательностей. Чем больше приспособленность хромосомы, тем больше у нее будет потомков в новом поколении. Начальная популяция Р ( t 0) формируется из Np случайных хромосом, формирование новой популяции выполняется на основе модели рулетки. [1]
Вычисляются приспособленность хромосом популяции ( целевая функция) и средняя приспособленность всей популяции. [2]
Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. [3]
Согласно блок-схеме генетического алгоритма ( рис. 4.3) производится возврат ко второму этапу, т.е. к оценке приспособленности хромосом из вновь сформированной популяции, которая становится текущей. [4]
Из этого следует, что если схема S содержит хромосомы со значением функции приспособленности, превышающим среднее значение ( т.е. приспособленность схемы S на k - Л итерации оказывается большей, чем среднее значение функции приспособленности хромосом из популяции P ( k), и поэтому F ( S, k) I F ( k) 1), то ожидаемое количество хромосом из родительского пула M ( k), соответствующих схеме S, будет больше количества хромосом из популяции P ( k), соответствующих схеме S. Поэтому можно утверждать, что селекция вызывает распространение схем с приспособленностью лучше средней и исчезновение схем с худшей приспособленностью. [5]
После обучения оценивается приспособленность каждой особи, входящей в текущую популяцию. Заметим, что также как и в примере максимизации функции ( пример 4.5), для оценивания приспособленности хромосом необходимо их вначале декодировать и лишь затем рассчитать значения функции приспособленности особей по их фенотипам. [6]
Нижние левые графики на рис. 4.27 - 4.31 показывают изменения наихудшего ( верхняя кривая) и среднего значения функции приспособленности особей популяции при смене поколений. Комплексная динамика средних значений функции приспособленности на протяжении всех поколений демонстрируется на рис. 4.34. Обратим внимание на то, что значения функции приспособленности наихудших хромосом в отдельных популяциях довольно велики и, очевидно, значительно отличаются от оптимального значения. [7]
Приспособленность произвольной хромосомы р определяется расстоянием по Хеммингу p ( pi, рт) между pi и рт ( числом несовпадающих компонент в этих наборах), причем f ( pi) экспоненциально уменьшается с ростом p ( pi, рт, т.е. чем больше различие между pi и рт, тем меньше ее приспособленность. Новое поколение Pt l получается из старого Р путем отбора и мутации последовательностей. Чем больше приспособленность хромосомы, тем больше у нее будет потомков в новом поколении. Начальная популяция Р ( t 0) формируется из Np случайных хромосом, формирование новой популяции выполняется на основе модели рулетки. [8]
Генетический алгоритм должен найти одну из этих точек. На рис. 4.103 представлены начальные значения переменных х1 и х2, которые введены в исходную популяцию в качестве генов одной из хромосом. Понятно, что данная хромосома будет очень скоро исключена из популяции, что подтверждается рис. 4.104. На этом рисунке показаны хромосомы популяции для t 30 ( после 30 тактов), что соответствует первой итерации ( первому поколению) классического генетического алгоритма. Переменные varl и var2 обозначают соответственно х -, и х2, первый столбец ( result) содержит значения функции приспособленности конкретных хромосом. Первое значение ( 20410) принадлежит особи, исключенной из популяции. На ее место вводится новая хромосома с аллелями, равными 7 89 и - 1 537, для которой значение функции приспособленности еще только предстоит рассчитать. В левом нижнем углу рисунка демонстрируется разнородность особей этой популяции. В данном случае она также довольно велика. На рис. 4.105 приведены аналогичные графики для популяции после 60 тактов ( f 60), а также столбчатая диаграмма, иллюстрирующая конкретные особи. [9]
 |
Блок-схема генетического алгоритма. [10] |
Селекция хромосом заключается в выборе ( по расчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки ( roulette wheel selection), который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. [11]
Страницы: 1