3. Требования к защите лабораторной работы

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

Контрольные вопросы

1. Общая идея методов случайного поиска.

2. Сравнение методов случайного поиска с линейной и нелинейной тактикой.

3. Сравнение детерминированных методов и методов случайного поиска.

4. Задача адаптации поиска.

Лабораторная работа № 6 эволюционный бионический алгоритм

Цель работы: Изучение работы методов оптимизации с глобальными свойствами на примере бионического эволюционного алгоритма.

1. Описание метода

Идея эволюционного метода базируется на том, что на начальном этапе имеем N произвольных точек, моделирующих отдельные особи. Среди N точек выбираем лучшую точку N^*. Степень приспособленности каждой из точек определяется значением функции Y(x): чем меньше значение функции, тем больше приспособлена особь и имеет больше шансов на выживание.

N^* лучших точек дают потомство, т.е. генерируются точки, отличающиеся от родителя случайным образом:

X_ij = X_j + ξ_ij, i = 1..N, j =1..K_j

где K_j – количество точек, сгенерированных вокруг, j-ой точки;

ξ_ij – случайные отклонения, моделирующие отличие i-го потомка от j-го родителя в силу случайных мутаций (скачкообразное изменение или появления нового признака у потомка). Среди потомков вступает в действие естественный отбор, при котором с большей вероятностью выживает потомок с минимальным значением функции (т.е. среди полученных потомков выбираем N^** - лучших).

Процедура повторяется до тех пор, пока не будет достигнуто фиксированное число реализованных поколений.

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

2. Порядок выполнения работы

1. Разработать алгоритм и программу поиска глобального максимума многоэкстремальной функции

при ограничениях:

• параметрических

;

• функциональных

2. Осуществить несколько запусков программы при различных параметрах алгоритма (число начальных точек, число генерируемых потомков и т.д.).

3. При отображении сгенерированных точек на дисплее точки каждого поколения изображаются различными цветами.

3. Требования к защите лабораторной работы

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

Контрольные вопросы

1. Характеристики алгоритмов с глобальными свойствами.

2. Параметрическая адаптация эволюционного бионического алгоритма.

Литература

1. Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.

2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука, 1988.

3. Первозванский А.А. Поиск. М., Наука, 1975.

4. Растригин Л.А. Случайный поиск. М., Знание, (Новое в жизни, науке и технике. Серия «Математика, кибернетика», 1), 1979.

5. САПР, в 9 кн. (под ред. Норенкова И.П.) М.: Высш. шк., 1986.

6. Фурунжиев Р.И. Вычислительная техника и ее применение. Мн.: Выш.шк., 1984.

Приложение