Оценка эффективности генетического алгоритма | MetodPro.ru

Реклама на сайте

Оценка эффективности генетического алгоритма


Рассмотрим простейший случай традиционного варианта генетического алгоритма, предполагая, что:

1)      цепочки символов в хромосомах бинарны. Ski = 0 или 1

2)      Длина цепочек постоянно равна N = const

3)      Отбор пропорционально-вероятностный.

4)      Рекомбинации отсутствуют. Есть только точечные мутации (случайные, равновероятностные замены символов).

5)      Численность популяции постоянна.

6)      Будем считать, что приспособленности особей определяются Хемминговой мерой близости, т.е. имеется одна оптимальная особь Sm,а приспособленности других особей экспоненциально уменьшаются с ростом расстояния по Хеммингу между рассматриваемой S и оптимальной хромосомой Sm. Предполагая, что интенсивность отбора достаточно велика, то считают, что основное время эволюции лимитируется мутациями. При чем, если мутации велики, то возможны потери уже найденных особей, а если мутации малы, то это замедляет эволюционные процессы. Разумно выбрать такую интенсивность мутаций, чтобы за одно поколение в среднем менялся один символ в хромосоме, т.е. вероятность замены каждого символа Pm в процессе мутаций должна быть порядка N-1. Тогда, если пренебречь нейтральным отбором, то число поколений, требуемых для нахождения оптимума, составляет . Условие T < Tn. Это условие предполагаем выполненным на пределе, т.е. полагаем, что T == n. Общее число особей, участвующих в эволюции составляет nобщ = n*T. Комбинируя формулы 1 и 2, получаем, что nобщ == N2. Хотя оценки 1 и 3 являются достаточно грубыми, они важны с инженерной точки зрения – использую эти оценки, разработчик конкретного алгоритма может оценить ту вычислительную мощность, которая ему потребуется. С инженерной точки зрения так же важно то, что возможна аппаратная реализация многопроцессорных вычислительных устройств, эффективно реализующих генетический алгоритм, а именно – каждой особи популяции можно поставить в соответствие отдельный процессор. Тогда расчеты приспособленностей можно выполнять параллельным образом, что позволяет ускорить процесс оптимизации.



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем