ПОИСК Статьи Чертежи Таблицы Постановка задачи поиска оптимальных решений с помощью генетических алгоритмов . Простой генетический алгоритм из "Основы автоматизированного проектирования " Эволюционные методы ЭМ) предназначены для поиска предпочтительных решений и основаны на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому состоянию систем. [c.184] Важнейшим частным случаем ЭМ являются генетические методы и алгоритмы. Генетические алгоритмы основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции. [c.185] Свойства объектов представлены значениями параметров, объединяемыми в запись, называемую в ЭМ хромосомой. В ГА оперируют хромосомами, относящимися к множеству объектов — популяции. Имитация генетических принципов — вероятностный выбор родителей среди членов популяции, скрещивание их хромосом, отбор потомков для включения в новые поколения объектов на основе оценки целевой функции — ведет к эволюционному улучшению значений целевой функции (функции полезности) от поколения к поколению. [c.185] Вычислительный процесс начинается с генерации исходного поколения — множества, включающего N хромосом (iV- размер популяции). Генерация выполняется случайным выбором аллелей каждого гена. [c.186] Для каждого витка внешнего цикла генетического алгоритма выполняется внутренний цикл, на котором формируются экземпляры нового (следующего за текущим) поколения. Во внутреннем цикле повторяются операторы выбора родителей, кроссовера родительских хромосом, мутации, оценки приспособленности потомков, селекции хромосом для включения в очередное поколение. [c.186] Рассмотрим алгоритмы выполнения операторов в простом генетическом алгоритме. [c.186] Правило (4.31) называют правилом колеса рулетки. Если в колесе рулетки выделить секторы, пропорциональные значениям F — F., то вероятности попадания в них суть Р., определяемые в соответствии с (4.33). [c.187] Кроссовер (скрещивание). Кроссовер, иногда называемый кроссингове-ром, заключается в передаче участков генов от родителей к потомкам. При простом (одноточечном) кроссовере хромосомы родителей разрываются в некоторой позиции, одинаковой для обоих родителей, выбор места разрыва равновероятен, далее происходит рекомбинация образующихся частей родительских хромосом, как это показано в табл. 4.3, где разрыв подразумевается между пятым и щестым локусами. [c.187] Мутации. Оператор мутации вьшолняется с некоторой вероятностью Р , т. е. с вероятностью Р происходит замена аллеля случайным значением, выбираемым с равной вероятностью в области определения гена. Именно благодаря мутациям расширяется область генетического поиска. [c.187] Селекция. После каждого акта генерации пары потомков в новое поколение включается лучший экземпляр пары. [c.187] Внутренний цикл заканчивается, когда число экземпляров нового поколения станет равным N. Количество повторений G внешнего цикла чаще всего определяется автоматически по появлению признаков вырождения (стагнации) популяции, но с условием не превышения заданного лимита машинного времени. [c.187] Вернуться к основной статье