Генетический методГенетический метод сочетает направленный поиск, основанный на эвристиках, с элементами случайности, цель которых – исключение «застревания» поиска в точках локального оптимума. • хромосома – любое решение задачи синтеза, т.е. определенным образом организованная совокупность выходных параметров, характеризующих решение задачи; • гены – поля хромосом, содержащие значения проектных параметров (аллели); • начальная популяция – исходное множество решений; • кроссинговер (кроссовер) – оператор, осуществляющий скрещивание хромосом, т. е. взаимный обмен генами между хромосомами предварительно выбранной пары родителей, порождающий пару новых решений; • мутация – случайное перестроение генов отдельных решений – порождает новые решения и служит для исключения «застревания» поиска в точках локального оптимума. Сущность метода: Задается начальная популяция и рассчитываются значения локальной целевой функции. Выбирается лучшее решение и копируется на место худшего (селекция и репродукция). Определяется пара родителей: –случайным образом, при этом вероятность выбора хромосом с лучшими значениями целевой функции должна быть выше; – по лучшему значению целевой функции (детерминированно). – Применяется кроссинговер и рассчитывается целевая функция для полученной пары решений. Гены, подлежащие обмену: – могут выбираться случайно с учетом получения допустимых решений, при этом вероятность выбора может зависеть от значения целевой функции; – назначаться детерминированно. Выполняется замещение родительской пары полученной парой или исключение из нового множества решений пары с худшими значениями целевой функции. Осуществляется мутация случайного или выбранного гена и оценка полученного решения. Для завершения процесса могут использоваться те же условия, что и у итерационного метода.
Алгоритмы, реализующие генетический метод, гарантируют получение лишь приближенного решения. Обладая достоинствами детерминированных алгоритмов (большей эффективностью по сравнению с вероятностными), генетические алгоритмы за счет использования вероятностного подхода при селекции, выборе пары родителей, работы кроссинговера и мутации должны быть лишены таких недостатков, как попадание в локальные экстремумы и зацикливание. Максимальное усиление любого из достоинств генетического метода способно свести остальные его преимущества на нет, превращая его в чисто вероятностный или полностью детерминированный метод. Простейшим примером вырожденного случая является итераци-онный алгоритм парных обменов, в котором репродуцируется одно начальное решение и выполняется парный обмен генов, т. е. скрещивание хромосом.
|
