17419

Генетичні алгоритми

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторна робота № 6 Генетичні алгоритми Мета: отримати навички розвязання практичних задач за допомогою генетичних алгоритмів. 5.1. Теоретичні відомості Генетичні алгоритми ГА Holland 19691990 спрощено моделюють процеси природної еволюції і засновані на стохасти

Украинкский

2013-07-01

89.5 KB

5 чел.

Лабораторна робота № 6

Генетичні алгоритми

Мета: отримати навички розв’язання практичних задач за допомогою генетичних алгоритмів.

5.1. Теоретичні відомості

Генетичні алгоритми (ГА) (Holland, 1969-1990) спрощено моделюють процеси природної еволюції і засновані на стохастических принципах.

Генетичні алгоритми зводяться до виконання наступних етапів:

1. Ініціалізувати популяцію.

2. Обчислити значення критерію якості для кожної особини популяції.

3. Виконати процес відтворення для кожної особини популяції.

4. Виконати схрещування і мутацію для кожної особини популяції.

5. Повернутися до п. 2, якщо не виконано умову завершення.

Реалізація ГА зводиться до операцій з рядками: копіювання рядків, заміни фрагментів рядків і інверсії бітів. Розглянемо приклад.

Приклад.

Знайти

,    де     .

Функція залежить від однієї цілочисельної змінної. Особин популяції доцільно представити у вигляді бінарного рядка довжиною 1 байт.

0

00000000

1  

00000001

...

255  

11111111

Число особин популяції в реальних задачах зазвичай складає 10–100. У даній задачі виберемо 8.

1. Ініціалізація — за допомогою датчика випадкових чисел у кожній з 8 позицій кожного рядка встановимо або 0 або 1.

Результати ініціалізації наведено в табл. 13.1.

Таблиця 5.1. Значення при ініціалізації

Особи  

 x  

fx

fnorm

10111101  

189  

0.733

0.144

11011000  

216  

0.471

0.093

01100011  

99  

0.937

0.184

11101100  

236  

0.243

0.048

10101110  

174  

0.845

0.166

01001010  

74  

0.788

0.155

00100011  

35  

0.416

0.082

00110101  

53  

0.650

0.128

Значення критерію якості — нормоване значення функції

.

3. Формування нової популяції з тим же числом особин. При формуванні нової популяції використовується принцип рулетки (рис. 5.1).

Результати застосування принципу рулетки показано в табл. 5.2.

Таблиця 5.2. Показники при формуванні покоління за принципом рулетки

   N

Рядок

Крит. якості

% співвідн.

1

01101

169

14.4

2

11000

576

49.2

3

10010

64

5.5

4

10011

361

30.9

Разом:

 

1170

100

Рис. 5.1. Співвідношення за критерієм якості

Ймовірність влучення в кожний із сегментів пропорційна його величині.

Генеруються 8 випадкових значень з діапазону [0,1]:

.

Якщо

тоді

.

Наприклад, якщо  [0, 0.144], то в нову популяцію включається . Якщо [0.144, (0.144+0.093)=0.237], то  включається в нову популяцію.

Таким чином максимальна імовірність включення в нову популяцію особин з максимальним значенням критерію якості.

Візьмемо набір з 8 випадкових чисел:

0.293, 0.971, 0.160, 0.469, 0.664, 0.568, 0.371, 0.109.

Індекси особин першої популяції, що ввійдуть у наступне покоління: 3, 8, 2, 5, 6, 5, 3, 1.

Після відтворення популяція матиме вигляд:

                               01100011

00110101

11011000

10101110

01001010

10101110

01100011

10111101

4. Схрещування — основна риса генетичного алгоритму полягає в обміні частин двох батьківських особин.

(a) Вибирається імовірність (приблизно 0.65–0.80) того, що між двома батьками відбудеться схрещування (виберемо = 0.75).

(б) Популяція випадковим образом розбивається на пари. Для будь-якої пари генерується випадкове число:

    .

Якщо

,

то пари піддаються схрещуванню.

(в) Для кожної з пар, що підлягають схрещуванню, випадковим чином задаються два числа (або одне число для одноточкового схрещування), що визначають границі рядка для обміну (табл. 5.3).

Таблиця 13.3. Значення при схрещуванні

Батьківська популяція

Нове покоління  

 x  

 f(x)

0111000211  

01110111  

119  

 0.999 

0011101201  

00100001  

33  

0.394

1110112000  

10101000  

168  

0.882

1101012110  

11011110  

222  

0.405

0120010110  

10001010  

138  

 0.998 

1021011110  

01101110  

110  

0.976

01100011  

01100011  

99  

0.937

10111101  

10111101  

189  

0.733

Оптимальне значення

 

10000000  

128

(г) Мутація — інвертування випадково обраних бітів (зазвичай з постійною імовірністю для кожного біта популяції, приблизно рівною 0.001–0.01).

Таким чином будь-який біт інвертується з імовірністю 0.1%–1%. Оскільки в наведеному прикладі число бітів у популяції складає 64, то при імовірності мутації =0.001 або 0.01 швидше за все жоден біт не змінить значення.

Тепер двом особинам нового покоління відповідає значення критерію якості >0.99.

5. Перехід до нової ітерації.

5.2. Порядок виконання роботи

1. Реалізувати генетичний алгоритм, використовуючи такі мови програмування як C++, Java, Fortran.

2. За допомогою генетичного алгоритму розв’язати задачу згідно з номером варіанту (розділ 5.3).

3. Результати роботи оформити звітом, який має містити: постановку задачі, опис послідовності дій при виконанні генетичного алгоритму із зазначенням всіх параметрів і проміжних результатів, результати роботи генетичного алгоритму та перевірка їх коректності, вихідний код програми.

5.3. Варіанти завдань

Реалізуйте генетичний алгоритм для розв’язання задачі максимізації функції:

1. f(x)=-(x-1)2/256, x  [0, 255].

2. f(x)=-(x2-3x+2)/256, x  [0, 255].

3. f(x)=-(x2-4x+15)2/256, x  [0, 255].

4. f(x)=-(x2-4x+3)/256, x  [0, 255].

5. f(x)=-(x2-6x+19)/256, x  [0, 255].

6. f(x)=-(2x2-5x+13)2/256, x  [0, 255].

7. f(x)=-(6x2-5x-1)2/256, x  [0, 255].

8. f(x)=-(4x2-4x+2)2/256, x  [0, 255].

9. f(x)=-(3x2-15)2/256, x  [0, 255].

10. f(x)=-(17x2-14x+15)2/256, x  [0, 255].


 

А также другие работы, которые могут Вас заинтересовать

76753. Ребра и грудина. Грудная клетка в целом 184.3 KB
  На позвоночном конце ребра находятся: головка с гребнем у IIX ребер и верхней нижней суставными поверхностями покрытыми гиалиновым хрящом у I XI и XII ребер гребень отсутствует; шейка переходящая углом в тело; на переходе бугорок на 10 верхних ребрах с двумя возвышениями: медиальнонижнее имеет суставную ямку для сочленения с поперечным отростком позвонка к другому возвышению прикрепляется связка; последние два ребра бугорка не имеют у первого ребра бугорок совпадает с вершиной угла. Тело ребра изогнутое у позвоночного конца...
76754. Развитие черепа в онтогенезе 191.91 KB
  Кости лицевого черепа развиваются на основе висцеральных дуг которых закладывается 5 пар а между ними 5 пар висцеральных карманов старое название жаберные дуги и жаберные карманы. Висцеральные дуги для лицевого черепа. Ядра точки окостенения подразделяются на: первичные 4150 появляющиеся во внутриутробном периоде в костях мозгового черепа их больше всего начало появления 78 недели к рождению они образуют 20 крупных очагов оссификации; вторичные появляющиеся после рождения; в больших костях черепа их мало но между костями в...
76755. Варианты и аномалии костей черепа 181.64 KB
  Теменные кости выраженность теменных бугров особенно у женщин; появление межтеменной кости. Затылочная кость наличие поперечного шва отделяющего верхнюю часть чешуи и образование вставочной дополнительной кости; присутствие более мелких добавочных костей часто расположенных в швах кости швов; значительная выраженность затылочных выступов; уплощение чешуи слабая выраженность борозд или наоборот увеличение изогнутости чешуи и углубление борозд; разнообразные формы большого отверстия костных валиков вокруг внутреннего его края;...
76756. Первая и вторая висцеральные дуги 187.99 KB
  Развитие лицевого (висцерального) черепа определяется мозгом и краниальным (глоточным) отделом первичной кишки, в котором на боковых стенках между висцеральными (жаберными) карманами появляются хрящевые висцеральные (жаберные) дуги, но особое значение для черепа имеют первые две.
76757. Кости лицевого черепа. Глазница 192.12 KB
  Подвисочная поверхность находится сзади тела образуя стенку подвисочной и крылонебной ямок состоит: из бугра верхней челюсти с задними альвеолярными отверстиями для одноименных нервов и сосудов. Глазничная поверхность занимает на теле кости верхнее положение участвуя в образовании нижней стенки глазницы. Носовая поверхность образует латеральную стенку полости носа. Небный отросток носовой гребень по медиальному краю; передняя носовая ость: окончание носового гребня впереди; верхняя носовая поверхность; нижняя небная поверхность...
76758. Височная кость 184.9 KB
  У верхушки пирамиды внутреннее отверстие сонного канала. На передней поверхности пирамиды находятся: каменисточешуйчатая щель хрящевая ростковая зона и отверстие мышечнотрубного канала; дугообразное возвышение от полукружных костных каналов лабиринта; крыша барабанной полости от среднего уха; тройничное вдавление на вершине пирамиды для одноименного нервного узла; расщелины и борозды большого и малого каменистого нервов. На задней поверхности пирамиды располагаются: внутреннее слуховое отверстие и внутренний слуховой проход для YII...
76759. Клиновидная кость 180.73 KB
  Клиновидная кость воздухоносная состоит из тела малых и больших крыльев и крыловидных отростков. На верхней поверхности тела находится турецкое седло а в нем: гипофизарная ямка для гипофиза центральной нейроэндокринной железы; бугорок седла кпереди от ямки; спинка седла с задними наклоненными отростками кзади от ямки; сонные борозды: правая и левая с клиновидными язычками лежат по боковым поверхностям седла предназначены для внутренней сонной артерии и внутреннего сонного симпатического нерва венозного пещеристого синуса. На...
76760. Крылонёбная ямка 181.89 KB
  Ямка соседствует и имеет связи с височной и подвисочной ямами. По форме ямка узкая щель ограниченная тремя выше перечисленными костями она граничит и сообщается с полостью черепа средней черепной ямой полостями носа и рта глазницей височной и подвисочной ямами. Крылонебная ямка сообщается: с полостью рта через большой и малый небные каналы с одноименными сосудами и нервами которые снабжают твердое и мягкое небо и небные миндалины; с полостью носа через клиновиднонебное отверстие с одноименными сосудами и нервами для слизистой...
76761. Полость носа 181.99 KB
  Полость носа обладает верхней нижней и парными боковыми стенками. Верхняя стенка состоит из: носовой части лобной кости продырявленной пластинки решетчатой кости и тела клиновидной которые составляют верхнезаднюю часть стенки; парных носовых костей: право и левой образующих передневерхнюю часть стенки. Нижняя стенка включает: небные отростки верхних челюстей и горизонтальные пластинки небных костей костное небо; носовой гребень который проходит по середине стенки в продольном направлении. Латеральные стенки правая и левая...