Часть полного текста документа:Генетические алгоритмы В.М. Курейчик Генетические алгоритмы (ГА) есть поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики. Они реализуют "выживание сильнейших" среди рассмотренных структур, формируя и изменяя поисковый алгоритм на основе моделирования эволюции [1-7]. Основой для возникновения генетических алгоритмов считается модель биологической эволюции и методы случайного поиска [ 6, 7 ]. Один из известных специалистов в мире в области случайного поиска и стохастической оптимизации Растригин пишет [ 6 ]. Случайный поиск (СП) возник как реализация простейшей модели эволюции, когда случайные мутации моделировались случайнымишагами оптимального решения, а отбор "уходом" неудачных вариантов. Например, для прикладных оптимизационных задач K(X) extr, здесь K- функционая, X- искомое решение, extr - экстремум (принимает в зависимости от условий задачи минимальное или максимальное значение). Тогда, например, для максимизации K(X) min X*, где X* - наилучшее решение. Это выражение реализуется с учетом ограничений и граничных условий. Эволюционный поиск согласно [6] - это последовательное преобразование одного конечного множества промежуточных решений в другое. Само преобразование можно назвать алгоритмом поиска или алгоритмом эволюции. Растригин выделяет три особенности алгоритма эволюции: - каждая новая популяция состоит только из "жизнеспособных" хромосом; - каждая новая популяция "лучше" (в смысле целевой функции) предыдущей; - в процессе эволюции последующая популяция зависит только от предыдущей [ 7 ]. Согласно [7] природа, реализуя эволюцию, как бы решает оптимизационную задачу на основе случайного поиска. Выделяется три основных бионических эвристики случайного поиска: - клеточный СП, - моделирование целесообразного поведения особей, - моделирование передачи наследуемой биологической информации. Законы эволюции отбирают все ценное и пригодное для эволюции и отметают в сторону, как мусор, как непригодное, все отсталое. Они не знают ни пощады ни состродания и производят оценку каждого лишь по степени пригодности или непригодности ею для дальнейшего развития. Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда [1,2]. Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей - стрингов (хромосом). Затем ГА применяет множество простых операций к начальной популяции и генерирует новые популяции. ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация. Р е п р о д у к ц и я - процесс, в котором хромосомы копируются согласно их целевой функции (ЦФ). Копирование хромосом с "лучшим" значением ЦФ имеет большую вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР), является искусственной версией натуральной селекции, "выживания сильнейших" по Дарвину. После выполнения ОР оператор кроссинговера (ОК) может выполниться в 3 шага. На первом шаге члены нового репродуцированного множества хромосом выбираются сначала. ............ |