Автор работы: Пользователь скрыл имя, 26 Февраля 2012 в 00:04, лабораторная работа
Вдоль прямой дороги расположены сёла. Дорога представлена целочисленной осью, а расположение каждого села – одним целым числом – координатой на оси. Никакие два села не имеют одинаковых координат. Расстояние между сёлами – это модуль разности их координат. В некоторых сёлах будут построены школы, координаты которых будут совпадать с координатами сёл. Школы нужно расположить так, чтобы общая сумма расстояний от каждого села до ближайшей школы была минимальной. Количество школ задаётся в начале решения.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ
Донецкий национальный технический университет
Институт информатики и искусственного интеллекта
Кафедра программного обеспечения интеллектуальных систем |
Д080404.1.02.08/106.ЛР
Лабораторная работа №1
по дисциплине: «Генетические алгоритмы»
Тема: «Построение простого генетического алгоритма для решения задач комбинаторной оптимизации»
Проверили: _________________ Волченко М.В. (дата, подпись) _________________ Степанов В.С. (дата, подпись)
Выполнил: | ||
| _________________ | ст. гр. СИИ-08А |
| (дата, подпись) | Седаков Е.В. |
|
|
|
|
|
|
Донецк 2012 | ||
Тема: Построение простого генетического алгоритма для решения задач комбинаторной оптимизации
Вариант 19
Индивидуальный вариант задания:
Вдоль прямой дороги расположены сёла. Дорога представлена целочисленной осью, а расположение каждого села – одним целым числом – координатой на оси. Никакие два села не имеют одинаковых координат. Расстояние между сёлами – это модуль разности их координат. В некоторых сёлах будут построены школы, координаты которых будут совпадать с координатами сёл. Школы нужно расположить так, чтобы общая сумма расстояний от каждого села до ближайшей школы была минимальной. Количество школ задаётся в начале решения.
Ход работы
1)Определить возможность решение задачи с помощью простого генетического алгоритма
Данная задача является задачей полного перебора, поэтому для её решения определённо можно применить генетический алгоритм.
2)Определить, описать и аргументировать способ кодирования хромосом.
Так как координаты школ и сёл по условию совпадают, будет разумно использовать двоичное кодирование. Длина хромосомы будет равна количеству сёл.
3)Определить фитнесс-функцию.
4)Определить штрафную функцию.
, true=1,false=0
- фитнесс-функция, совмещённая со штрафной. Делает вероятность использования неподходящей хромосомы тем меньше, чем хуже она подходит.
5)Выбрать и аргументировать размер популяции.
Для задачи с шестью сёлами мы получим 64 возможных комбинации. 20% от этого числа – это примерно 12. Таким и будет размер популяции.
6)Выбрать генетические операторы.
Пропорциональный отбор, одноточечный кроссинговер, мутация с вероятностью 4%, элитизм одной хромосомы.
7)Предложить критерий останова.
Совпадение фитнесс-функции в течение трёх поколений.
Расположение сёл: 1,2,4,5,6,8
Для случаев равного расстояния, учитывается первая попавшаяся школа.
| H | FF | SF | H | FF | SF | H | FF | SF |
1 | 111011 | 0 | 1 | (elit)100101 | 1/3 | 0 | (elit)100101 | 1/3 | 0 |
2 | 101010 | 1/5 | 0 | (2+5)101010 | 1/5 | 0 | (1+2)100010 | 0 | 1 |
3 | 000000 | 0 | 1 | (8+2)101010 | 1/5 | 0 | (1+1)100101 | 1/3 | 0 |
4 | 001010 | 0 | 1 | (8+9)100001 | 0 | 1 | (2+3)101011 | 0 | 1 |
5 | 011010 | 1/5 | 0 | (11+8)101101 | 0 | 1 | (3+2)101010 | 1/5 | 0 |
6 | 001001 | 0 | 1 | (11+8)100101 | 1/3 | 0 | (3+1)100101 | 1/3 | 0 |
7 | 111111 | 0 | 1 | (11+2)101110 | 0 | 1 | (10+3)100110 | ¼ | 0 |
8 | 100101 | 1/3 | 0 | (8+5)111010 | 0 | 1 | (10+6)100101 | 1/3 | 0 |
9 | 110001 | 1/11 | 0 | (5+5)011011 | 0 | 1 | (6+2)101010 | 1/5 | 0 |
10 | 101101 | 0 | 1 | (8+8)100101 | 1/3 | 0 | (6+6)100101 | 1/3 | 0 |
11 | 101100 | 1/5 | 0 | (11+9)101101 | 0 | 1 | (2+6)101101 | 0 | 1 |
12 | 100011 | ¼ | 0 | (5+8)011011 | 0 | 1 | (1+1)100101 | 1/3 | 0 |
Вывод: в данной лабораторной работе я применил механизм генетических алгоритмов для решения задачи полного перебора и уже в третьем поколении получил удовлетворительное решение.