|
24 х гены, изменяющиеся значения в определенных позициях которых называются аллелями. При кодировании как правило используется двоичное представление переменных. 3. Каждая хромосома хь в популяции декодируется в необходимую форму для оценки приспособленности и ей присваивается значение эффективности 1х (Х[) в соответствии с функцией оптимальности. 4. Каждой хромосоме присваивается вероятность воспроизведения рь 1 = Р, является функцией эффективности данной хромосомы. 5. В соответствии с вероятностями воспроизведения р( выбираются наиболее приспособленные хромосомы для воспроизведения. Хромосомы производят потомков, используя операции рекомбинации: кроссинговер (хромосомы скрещиваются, обмениваясь генами) и мутация (вероятностное изменение генов). 6. Процессы воспроизведения новых поколений и оценки приспособленности потомков циклически повторяются. Процесс останавливается, если получено решение удовлетворяющее заданным критериям оптимальности, либо если исчерпано отведенное на поиск решения время. Формально генетический алгоритм можно описать следующим образом [60]: ГА=(Р°,Л,1,з,р,/() ( 1.1), где Р° (а0/, .... а0д) исходная популяция, а -,решение задачи, представленнос в виде хромосомы; Я целое число ( размер популяции); / целое число (длина каждой хромосомы, популяции); ^ оператор отбора; р отображение, определяющее рекомбинацию'(кроссинговер, мутация);/—функция пригодности; I —критерий останова. X В текущий момент ГА являются-наиболее популярными эволюционными алгоритмами, что связано с простотой реализации и достаточным уровнем абстракции естественных процессов эволюции, который реализован в ГА. |
35 присваивается значение эффективности р. (Х) в соответствии с функцией оптимальности. 4. Каждой хромосоме присваивается вероятность воспроизведения Рь [= которая зависит от эффективности данной хромосомы. 5. В соответствии с вероятностями воспроизведения р1 создается новая популяция хромосом, причем с большей вероятностью воспроизводятся наиболее эффективные элементы. Хромосомы производят потомков, используя операции рекомбинации: кроссинговер (хромосомы скрещиваются, обмениваясь частями строк) и мутация (вероятностное изменение аллелей). 6. Процесс останавливается, если получено удовлетворительное решение, либо если исчерпано отведенное на эволюцию время. Если процесс не окончен, то вновь повторяются процессы оценки и воспроизведения новой популяции. Формально генетический алгоритм можно описать следующим образом [103]: Г А = {Р °,Х ,1,8,р,/,П где = (а01, а )) — исходная популяция, а°( — решение задачи, представленное в виде хромосомы; Л—целое число ( размер популяции); / — целое число (длина каждой хромосомы популяции); 5 —оператор отбора; р — отображение, определяющее рекомбинацию (кроссинговер, мутация); / — функция пригодности; ¿-критерий останова. В текущий момент ГА являются наиболее популярными эволюционными алгоритмами, что связано с простотой реализации и достаточным уровнем абстракции естественных процессов эволюции, который реализован в ГА. Генетическое программирование [152, 153] представляет собой одно из направлений в ЭМ и ориентировано в основном на решение задач автоматического синтеза программ на основе обучающих данных путем индуктивного вывода. Хромосомы или структуры, которые автоматически |