Название: Генетический алгоритм
Вид работы: курсовая работа
Рубрика: Информатика и программирование
Размер файла: 796.01 Kb
Скачать файл: referat.me-139886.docx
Краткое описание работы: Программа реализации генетического алгоритма, использование визуальной среды программирования. Руководство пользователя, листинг программы. Возможность ввода параметров: объем популяции, число поколений, коэффициент скрещивания и мутации, число городов.
Генетический алгоритм
Министерство образования и науки Республики Казахстан
Карагандинский Государственный Технический Университет
Кафедра САПР
Пояснительная записка
к курсовой работе
по дисциплине: "Прикладная теория систем"
Тема: "Генетический алгоритм"
2009
Цель работы
Выработать способность системного рассмотрения проблем и задач и дать методологию и методы их решения (вне зависимости от их проблемной ориентации). Получить практические навыки разработки базовых понятий аксиоматики, методологии исследования проектирования сложных систем. Разработка концептуальных формализованных средств, представление объектов и процессов как сложную систему. Построение обобщённых моделей, объектов и процессов как систему логико-математического аппарата их анализа и синтеза. Разработка иерархического строения систем, их целенаправленного поведения, управления и оптимизации. Научиться формализовано представлять задачу в терминах характеристик её решения, формировать наиболее адекватный критерий эффективности оценки решения, применять для этого генетический алгоритм.
Задача:
Разработать программу реализации генетического алгоритма в соответствии с выданным вариантом. Для разработки использовать любую визуальную среду программирования.
В интерфейсе программы предусмотреть возможность ввода параметров:
объём популяции;
число поколений;
коэффициент скрещивания;
коэффициент мутации;
для дифференциального кроссовера коэффициенты k,c;
для задачи коммивояжёра ввод [4. .40] числа городов и их расстановку вручную и автоматически;
для биологической задачи возможность ввода названий характеристик [10.15], их значений [4. .40], значимости и веса [0.1] каждой характеристики.
Результаты работы программы должны включать:
на каждом шаге отображать номер поколения и лучшее значение фитнес-функции в этом поколении;
лучшее значение фитнес-функции за все поколения и соответствующую ей структуру особи;
для биологической задачи и задачи оптимизации функции график зависимости значения целевой функции от номера поколения;
для задачи коммивояжёра на каждом поколении графически отображать лучщий маршрут.
Интерфейс программы должен включать характеристики генетического алгоритма в соответствии с вариантом, сведения о разработчике, краткую справку (руководство пользователя).
Вариант задания:
Тип задачи - коммивояжёр
Выбор пары - панмиксия
Кроссовер - двухточечный
Мутация - перестановка
Отбор - элитный
Критерий останова - количество поколений
Выходные данные – карта.
Анализ результатов моделирования на основе разработанной программы представляется в виде таблицы:
№ эксперимента |
Кол-во маршрутов |
Число поколений |
Коэф. скрещивания |
Коэф. мутации |
Фитнес- функция (min) |
| 1 | 100 | 500 | 0,5 | 0,001 | 3110 |
| 2 | 150 | 500 | 0,5 | 0,001 | 2783 |
| 3 | 200 | 500 | 0,5 | 0,001 | 2697 |
| 4 | 200 | 1000 | 0,5 | 0,001 | 3034 |
| 5 | 200 | 1500 | 0,5 | 0,001 | 2817 |
| 6 | 200 | 2000 | 0,5 | 0,001 | 3088 |
| 7 | 200 | 500 | 1 | 0,001 | 3282 |
| 8 | 200 | 500 | 1,5 | 0,001 | 3296 |
| 9 | 100 | 500 | 1 | 0,001 | 3334 |
| 10 | 100 | 500 | 0,5 | 0,01 | 3025 |
| 11 | 200 | 500 | 0,5 | 0,01 | 2511 |
| 12 | 100 | 500 | 1 | 0,01 | 2852 |
| 13 | 200 | 500 | 1 | 0,01 | 2749 |
| 14 | 100 | 500 | 0,5 | 0,1 | 3221 |
| 15 | 200 | 500 | 1 | 0,1 | 2497 |
Вывод:
Анализируя полученные результаты моделирования приходим к выводу, что оптимальным количеством маршрутов можно считать 200, число поколений, нет необходимости повторять алгоритм больше 500 раз (поколений), чтобы получить хороший результат. Также на значение фитнес-функции влияет коэффициент скрещивания: оптимальный коэффициент скрещивания - 1, коэффициент мутации также играет большую роль в моделировании генетического алгоритма, оптимальный коэффициент мутации - 0,1. Как видно из таблицы самое лучшее значение фитнес-функции, а значит самое минимальное расстояние за которое можно объехать 20 городов, получают за счет параметров, которые указаны в таблице в строке под номером 15.
Руководство пользователя.
Для того, чтобы открыть программу необходимо мышью дважды кликнуть по файлу “Коммивояжёр. exe”. Также необходимо проверить наличие графического документа под названием “map. bmp" в исходной папке (месте).
На экране монитора появится главное окно программы, как показано на Рис. 1
Рис. №1 Главное окно программы
В данной программе города можно задавать как вручную, для этого необходимо на карте кликнуть мышью в нужном месте, так и автоматически. Чтобы задать города автоматически необходимо в правом верхнем углу окна программы выбрать "Задать города автоматически" как показано на рис. №2.
Рис. №2
Затем ниже необходимо ввести количество городов и нажать на кнопку "Сгенерировать города". При необходимости можно очистить поле ввода городов, т.е. удалить имеющиеся города на карте нажав кнопку "Удалить города".
После того, как на карте будут отмечены необходимое количество городов (4-40), для того, чтобы застить алгоритм поиска минимального пути необходимо нажать кнопку "Поиск". Процент выполнения моделирования представлен ProgressBar-ом, который находится под картой рис. № 3.
Рис № 3. ProgressBar
По окончанию моделирования, а это произойдет тогда, когда ProgressBarполностью заполнится синим цветом, результат отобразится под ProgressBar-ом рис. № 4.
Рис. №4 Результат моделирования
Также на карте будет прорисован самый оптимальный маршрут рис. № 5.
Рис. №5 Оптимальный маршрут
Также в программе предусмотрено изменение основных параметров, которые влияют на результат моделирования рис. № 6.
Рис. № 6. Изменяемые параметры
Листинг программы
unitUnit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls;
type
TForm1 = class (TForm)
Image1: TImage;
Button1: TButton;
Edit1: TEdit;
Label1: TLabel;
Edit2: TEdit;
Label2: TLabel;
Edit3: TEdit;
Label3: TLabel;
Edit4: TEdit;
Label4: TLabel;
Edit5: TEdit;
Label5: TLabel;
procedure Image1MouseDown (Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure Image1Click (Sender: TObject);
procedure FirstGeneration (Sender: TObject);
procedure CreaChildren (Sender: TObject);
procedure Mutation (Sender: TObject);
procedure TrackRead (Sender: TObject);
procedure DrawMarsh (Sender: TObject);
function CrossOver (p,m: integer): string;
procedure Mixer (Sender: TObject);
procedure Button1Click (Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
pX,pY,elite: array of integer; // координаты городов, элитные
road: array of integer;
parents: array of string; // поколений родителей, детей; результат
child: array of string;
result: array of string;
gl: integer; // количество элитных
nCity,nMarsh: integer; // количество городов, маршрутов
kMut,kCross: real; // коэффициент мутации, скрещивания
implementation
{$R *. dfm}
procedure TForm1. Mixer (Sender: TObject);
var
i,j,n,k: integer;
s: string;
label lbl4;
BEGIN
n: =round ( (nMarsh) *kCross) - 1;
for i: =0 to nMarsh-1 do
begin
setLength (child,n+i+2);
child [n+i+1]: =parents [i] ;
end;
TrackRead (sender);
setlength (elite,1);
s: ='_';
{1}for i: =0 to nMarsh-1 do
begin
lbl4:
elite [0]: =random (n+nMarsh);
if pos ('_'+inttostr (elite [0]) +'_',s) <>0 then goto lbl4;
for j: =0 to n+nMarsh-1 do
begin
if pos ('_'+inttostr (j) +'_',s) =0 then
begin
if road [elite [0]] >road [j] then
begin
elite [0]: =j;
end;
end;
end;
s: =s+inttostr (elite [0]) +'_';
parents [i]: =child [elite [0]] ;
{1}end;
END;
function TForm1. CrossOver (p,m: integer): string;
var
gen: char;
i,j: integer; // счетчика
t1,t2: integer; // точки кроссовера
nC,kC: integer; // границы цикла
papa,mama: string;
label lbl3;
BEGIN
papa: =parents [p] ;
mama: =parents [m] ;
randomize;
t1: =random (nCity-1) +1; // выбираем 1 точку
lbl3:
t2: =random (nCity-1) +1; // выбираем 2 точку
if t2=t1 then goto lbl3; // 1 точка не 2 точка
if t1<t2 then // выбираем границы цикла
begin
nC: =t1;
kC: =t2;
end
else
begin
nC: =t2;
kC: =t1;
end;
for i: =nC to kC do // цикл скрещивания
begin
if pos (mama [i],papa) =0 then // проверка на совпадение генов
begin
delete (papa, i,1);
insert (mama [i],papa, i); // добавляем материнские гены
end
else
begin // изменяем повторившийся ген
gen: =papa [i] ;
papa [i]: =papa [i+1] ;
papa [i+1]: =gen;
end;
end;
crossover: =papa; // возварщаем значение функции потомка
END;
procedure TForm1. TrackRead (Sender: TObject);
var
i,j: integer;
p1,p2: integer;
p: string;
BEGIN
{1}for i: =0 to length (child) - 1 do // большой цикл по маршрутам
begin
setlength (road, i+1);
p: ='';
p: =child [i] ;
{2}for j: =1 to nCity-1 do // внутренний цикл по городам маршрутов
begin
if j<>nCity-1 then // проверка на последний город
begin
p1: =StrToInt (p [j]); //
p2: =StrToInt (p [j+1]); // соседний
end
else
begin
p1: =StrToInt (p [j+1]); // последний
p2: =StrToInt (p [1]); // первый
end; // расчет расстояния
road [i]: =road [i] +round (sqrt (sqr (pX [p1] -pX [p2]) +sqr (pY [p1] -pY [p2])));
{2}end;
{1}end;
END;
procedure TForm1. DrawMarsh (Sender: TObject);
var
i,j: integer;
p1,p2: integer;
p: string;
BEGIN
p: =parents [0] ;
Image1. CleanupInstance;
with Image1. Canvas do
begin
for j: =1 to nCity do // внутренний цикл городам маршрута
begin
if j=nCity then
begin
p1: =StrToInt (p [j]);
p2: =StrToInt (p [1]);
end
else
begin
p1: =StrToInt (p [j]);
p2: =StrToInt (p [j+1]);
end;
MoveTo (pX [p1],pY [p1]);
LineTo (pX [p2],pY [p2]);
end;
end;
END;
procedure TForm1. Mutation (Sender: TObject);
var
i,ran: integer; // счетчик, случайное число
gen: char; // мутирующий ген
mutant: string;
BEGIN
mutant: ='';
for i: =0 to round ( (nMarsh) *kCross) - 1 do // цикл мутации
begin
randomize;
if kMut<random (10) /100 then // проверка на мутацию
begin
mutant: =child [i] ; // мутирующая особь
ran: =random (nCity-1);
gen: =mutant [ran] ; //
mutant [ran]: =mutant [ran+1] ; // мутируем
mutant [ran+1]: =gen; //
child [i]: =mutant;
end;
end;
END;
procedure TForm1. FirstGeneration (Sender: TObject);
var
i,j,ram: integer; // счетчики, рандомное значение
s: string; // строка маршрута
label lbl1; // метка
BEGIN
randomize;
for i: =0 to nMarsh-1 do // цикл формирования первого поколения
{1}begin
s: ='';
setlength (parents, i+1); // устанавливаем длину массива родителей
for j: =0 to nCity-1 do // цикл формирования строки маршрута
{2}begin
setlength (s,j+1); // устанавливаем длину строки маршрута
lbl1:
ram: =random (nCity); // случайный выбор номера города
if pos (IntToStr (ram),s) =0 then // проверка на повтор номера города
begin
insert (IntToStr (ram),s,1); // добавление номера города в строку маршрута
end
else goto lbl1; // переход на метку
{2}end;
parents [i]: =s; // заполняем массив родителей (первое поколение)
{1}end;
END;
procedure TForm1. CreaChildren (Sender: TObject);
var
i: integer; // счетчики
p,m: integer; // номера родителей
label lbl2;
BEGIN
randomize;
for i: =0 to round ( (nMarsh) *kCross) - 1 do // цикл создания пар
begin
setlength (child, i+1);
p: = random (nMarsh); // выбираем номер папы
lbl2:
m: = random (nMarsh); // выбираем номер мамы
if m=p then goto lbl2; // папа не мама
child [i]: =crossover (p,m); // создаем потомков
end;
END;
procedure TForm1. Image1Click (Sender: TObject);
begin
inc (nCity); // считаем города
end;
procedure TForm1. Image1MouseDown (Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
// // /
with Image1. Canvas do
begin
Brush. Color: =clRed;
Brush. Style: =bsSolid;
Rectangle (x-5,y-5,x+5,y+5);
Brush. Color: =clWhite;
TextOut (x,y, inttostr (nCity));
end;
// // /
SetLength (pX,nCity+1);
pX [nCity]: =x;
SetLength (py,nCity+1);
pY [nCity]: =y;
// // /
end;
procedure TForm1. Button1Click (Sender: TObject);
var
i,nPokol: integer;
begin
nMarsh: =StrToInt (Edit3. Text);
kMut: =StrToFloat (Edit2. Text);
kCross: =StrToFloat (Edit4. Text);
nPokol: =StrToInt (Edit5. Text);
FirstGeneration (sender);
for i: =1 to nPokol do
begin
CreaChildren (sender);
Mutation (sender);
Mixer (sender);
DrawMarsh (sender);
end;
end;
end.
Похожие работы
-
Параллельный генетический алгоритм
Рассмотрена концепция параллельного генетического алгоритма. Определенны классы параллельных генетических алгоритмов. Определены проблемы построения параллельного генетического алгоритма и дальнейшие пути развития алгоритма.
-
Генетические алгоритмы
Основные генетические операторы. Схема функционирования генетического алгоритма. Задачи, решаемые с помощью генетических алгоритмов. Математическая постановка задачи оптимизации. Решение Диофантова уравнения. Программная реализация. Создание пособия.
-
Оптимизация отбора оптимальных признаков на основе приме-нения методов моделирования эволюции для задачи распозна-вания текста
Распознавание образов. Метод отбора оптимальных признаков. Генетическая модификация МООП.
-
Трассировка в коммутационном блоке на основе генетических процедур
Формулировка задачи, основные термины и обозначения. Структура хромосом, их кодирование и декодирование. Генетические операторы.
-
Генетические алгоритмы
Генетические алгоритмы (ГА) есть поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики. Они реализуют «выживание сильнейших» среди рассмотренных структур.
-
Генетический алгоритм глобальной трассировки
Проблемная формулировка, термины и обозначения. Разработка генетических процедур для задачи глобальной трассировки. Экспериментальные исследования генетического алгоритма глобальной трассировки.
-
Решение задачи одномерной упаковки с помощью параллельного генетического алго-ритма
В работе представлен паралелльный генетический алгоритм (ПаГА) для решения зада-чи одномерной упаковки. В целом эта задача является задачей разбиения множества объек-тов на непересекающиеся подмножества.
-
Перспективные архитектуры генетического поиска
В последнее время появились новые «нестандартные» архитектуры генетического по-иска, позволяющие в большинстве случаев решать проблему предварительной сходимости алгоритмов. Это методы миграции и искусственной селекции.
-
Интеллектуальные информационные технологии и системы: генетические алгоритмы
Содержание фундаментальной теории гена. Описание простого генетического алгоритма поиска оптимальных решений. Сущность понятий "кроссинговер", "сайт", "иллегальная рекомбинация". Этапы реализации алгоритма Девиса по перераспределению участков хромосом.
-
Разработка методов исследования характеристик генетического алгоритма распределе-ния цепей по слоям в МСМ
Одной из задач проектирования топологии матричных БИС и СБИС является задача оптимального распределения по слоям трассируемых соединений в базовом матричном кри-сталле.