Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Генетический алгоритм

Название: Генетический алгоритм
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 09:39:49 13 августа 2009 Похожие работы
Просмотров: 95 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра САПР

Пояснительная записка

к курсовой работе

по дисциплине: "Прикладная теория систем"

Тема: "Генетический алгоритм"

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.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:46:52 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:52:40 28 ноября 2015

Работы, похожие на Курсовая работа: Генетический алгоритм

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150883)
Комментарии (1841)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru