да. Лабораторной работы по дисциплине

• Название: Лабораторной работы по дисциплине
• Дата: 04.03.2022
• Размер: 261.07 Kb.
• Имя файла: 1lr_Klevakin.docx
• Тип: Решение; #382969

Министерство науки и высшего образования Российской Федерации

федеральное государственное бюджетное образовательное учреждение
высшего образования

”Алтайский государственный технический университет им. И. И. Ползунова”

Факультет информационных технологий

^{наименование подразделения}

Кафедра информатики, вычислительной техники

и информационной безопасности

^{наименование кафедры}

Направление Информатика и вычислительная техника

Отчёт защищен с оценкой_______
______________ А. Ю. Андреева

(^{подпись руководителя от вуза) (инициалы, фамилия)}
“ ”_____________2022_г.
ОТЧЁТ

по лабораторной работе № 1

Решение задач с использованием генетического алгоритма

^{тема лабораторной работы}

по дисциплине Введение в интеллектуальные системы
ЛР 09.03.01.09.000 O

^{обозначение документа}
Студент группы ИВТ-82 Д.Р. Клевакин

^{инициалы, фамилия}
Руководитель работы к.ф.-м.н. доцент А.Ю. Андреева

^{должность, ученое звание инициалы, фамилия}

Барнаул 2022

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

Задание: найти экстремум функции на заданном интервале методом генетического алгоритма.

Вариант 9

Функция:



Критерий останова – выполнение алгоритмом априорно заданного числа итераций.

Селекция – схема пропорционального отбора.

Скрещивание – универсальное.

Мутации – изменение случайно выбранного бита.
Код программы на языке Python

import random

import graycode

import numpy as np

import matplotlib.pyplot as plt
Q = 50 # количество поколений

MAX_ENT = 10 # размер популяции

MAX_CH = 5 # количество детей в одном цикле воспроизводства

N = 9 # длина хромосомы
X=0 #координаты точки, которая будет найдена в результате работы алгоритма

Y=0
# формируем x y

a=0

b=35

h=(b-a)/511

xm=np.arange(a,b+h,h)

fx= lambda x:(x-3)*(x-15)*(x-0.5)*(x-24)*(x-6)*np.sin(x)

ym=fx(xm[:])

plt.plot(xm,ym) #Экспонентное

plt.show()
fit_q = [[0 for _ in range(MAX_ENT)] for _ in range(Q)] # лучший из поколения
def fitness(inp): # inp – входной список из нулей и единиц

i=graycode.gray_code_to_tc(inp)

return ym[i]
# Начальное поколение

entity=[random.randint(0,512) for i in range(MAX_ENT)]
for q in range(Q): # цикл поколений - выполнение алгоритмом априорно заданного числа

# операций

# Считаем fitness для каждого организма

fit = [0 for _ in range(MAX_ENT)]

for i in range(MAX_ENT):

fit[i] = fitness(entity[i])

max_index=0

i=0

while(i
if(fit[i+1]>fit[i]):

max_index=i+1

i=i+1

INDEX=graycode.gray_code_to_tc(entity[max_index])

print('x=', xm[INDEX])

print('fit = ', max(fit))

X=xm[INDEX]

Y=max(fit)

# Запомнили лучшего в поколении

fit_q[q][:] = sorted(fit[:],reverse=True)
# Воспроизводство

fl_parent = [True for _ in range(MAX_ENT)] #до цикла воспроизводства все могут быть родителями
child1=0

child2=0

k=0

while (k < MAX_CH): # цикл воспроизводства 2*MAX_CH потомков

m1=random.randint(0,MAX_ENT-1) # первый кандидат родитель

m2=random.randint(0,MAX_ENT-1) # второй кандидат родитель

#print(k,m1,m2)

if (m1 == m2):

continue # должны быть разные

if not(fl_parent[m1] & fl_parent[m2]):

continue # кто-то уже имел потомка
l=random.randint(0,511)

child1=entity[m1]&l|entity[m2]&l

child2=entity[m1]&l|entity[m2]&l

# добавка к массиву организмов двух потомков

entity.append(child1)

entity.append(child2)
'''

for row in entity:

print(' '.join([str(elem) for elem in row]))

'''

fl_parent[m1]=False # больше потомков у особей не будет

fl_parent[m2]=False # в данном поколении

k+=1

# конец цикла воспроизводства

# МУТАЦИИ - изменение случайно выбранного бита
p_vm=0.1 # Вероятность мутации гена

p_m=0.2 # Вероятность победы менее приспособленного

mut_entity=0

for j in range(MAX_ENT+2*MAX_CH): # цикл по всем организмам вместе с потомками

if(random.random() < p_m): # инвертирование бита для мутанта

l=random.randint(1,8)

k=2**l

mut_entity=k^entity[j]

f1 = fitness(entity[j]) # приспособленность организма

f2 = fitness(mut_entity) # приспособленность мутанта

if (f1 > f2):

if(random.random() < p_vm): # останется менее приспособленный

entity[j]=mut_entity

else:

entity[j]=mut_entity # остается более приспособленный

# конец мутаций

# ЕСТЕСТВЕННЫЙ ОТБОР

tmp_entity=[]

sums=sum([fitness(g)+abs(min(ym)) for g in entity])

fl = [True for _ in range(MAX_ENT+2*MAX_CH)]

mas_ot=[0]

for i in entity:#ХРАНИТ ПРОМЕЖУТКИ

mas_ot.append(mas_ot[-1]+(fitness(i)+abs(min(ym)))/sums)

k=0

while k
l=random.uniform(0,1)

for j in range(MAX_ENT+2*MAX_CH):

if l>mas_ot[j] and mas_ot[j+1]>l:

if fl[j]:

tmp_entity.append(entity[j])

fl[j]=False

k+=1

break

entity=tmp_entity

# конец цикла естественного отбора
# конец цикла количества поколнеий Q
ym=fx(xm[:])

plt.plot(xm,ym)

plt.scatter(X, Y, c = 'r')

plt.show()


Тестирование



Рисунок 1 – Полученная функция на промежутке [0;35]


Рисунок 2 – Поиск экстремума на промежутке [0;35]