Информационная система "Конференции"

VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых)

29-31 октября 2005 года, г. Кемерово, Россия

Тезисы докладов

математическое моделирование

О модификации оператора равномерного скрещивания в генетическом алгоритме

Семенкина М.Е.

Cредняя школа № 7 (Красноярск)

Генетические алгоритмы представляют собой стохастическую оптимизационную процедуру, имитирующую процессы естественной эволюции. Генетические алгоритмы используют операторы селекции, рекомбинации (скрещивания), мутации и другие. Среди всех операторов рекомбинации только равномерное скрещивание позволяет производить полное исследование поискового пространства. Равномерное скрещивание осуществляется следующим способом: случайным образом для каждого гена потомка выбирается номер родителя, ген которого и передается потомку.

В обычном понимании равномерное скрещивание является равновероятным, так как ген каждого из родителей может передаться потомку с равной вероятностью, т.е. с одинаковой вероятностью потомок может получить ген, как родителя с высокой пригодностью, так и низкой. Поэтому на данном этапе не оказывается селективное давление. Для того, чтобы выяснить нужен ли отбор на этом уровне, необходимо разработать модификации равномерного скрещивания, которые будут учитывать пригодность родителей.

Можно предложить несколько вариантов того, каким образом пригодности родителей будут влиять на вероятность передачи гена. Первая модификация равномерного равновероятного скрещивания - это пропорционально-равномерное скрещивание: вероятность того, что ген именно этого родителя будет передан потомку, пропорциональна его пригодности. Вторая модификация - турнирно-равномерное скрещивание: организуется турнир, победитель которого передает свой ген потомку. Третья – рангово-равномерное скрещивание: согласно пригодности расставляются ранги, вероятность того, что ген этого родителя передастся потомку, пропорциональна рангу претендента, а не пригодности.

В результате экспериментов, проведенных на тестовых задачах, было выявлено: эффективность генетических алгоритмов, использующих модификации, не ниже эффективности генетического алгоритма со стандартным оператором, а на некоторых задачах даже выше. Следовательно, модификации равномерного скрещивания имеют право на существование, а алгоритмы с их применением требуют дополнительных исследований.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]