Тестовые данные (тест генетического алгоритма)

 
157 
151.000  
7  
1  
191.000  
10  
4 
208.000  
15  
4 
221.000  
8  
1  
 
 
Рис.1. Граф тестовой параллельной программы. Параллельная система 
гомогенна – 8 процессоров производительностью по 1, связанных друг 
с другом линиями пропускной способностью 5 в случае различных 
процессоров и с нулевым временем пересылки между одним и тем же 
процессором 
 
Максимальное  время  выполнения  последовательности  задач  «без 
пересылок» – в обведенной цепочке. Оно равно 221 (если всю цепочку 

158 
выполнить на одном процессоре), что практически и сделано ГА: оста-
лась только одна пересылка, потребовавшая единицу времени. Кроме 
того, в силу достаточно большого количества пересылок задействова-
но всего 5 процессоров из 8 и при этом расписание практически опти-
мально. Аналогичная ситуация наблюдалась при правильном подборе 
параметров ГА и на других тестах. 
Таблица 
Параметры данного теста 
Кол-во особей  
50 
% мутации 60 
% рекомбинации 30 
% мутации P
i 
10 
% мутации R
i 
10 
Средний % мутирующих генов 50 
Среднее кол-во точек скрещивания 1 
Мин. допустимая разница значений 0.01 
Кол-во «неулучшенных» популяций 32 
Макс. размер «штрафа», % 
150 
 
Таким образом, реально решение было найдено за 35 циклов (67–
32=35), а потом 32 цикла ГА не смог улучшить значение более чем на 
0.01 и остановился. Лишних циклов можно избежать, включив систему 
контроля времен простоя процессора. 
В  соответствии  со  свойствами  генетических  алгоритмов,  данный 
алгоритм также имеет свойство улучшать априори найденное решение, 
т. е. если решение примерно известно и подано на вход алгоритма как 
одна или несколько особей в начальной популяции, алгоритм быстрее 
(в среднем) надет нужное решение. 
Литература 
1.  Теория  расписаний  и  вычислительные  машины / Под  ред.  Э.Г 
Коффмана). 
2. Grant 
K. 
An introduction to genetic algorithms //C/C++ Users Journal, 
March 1995. P. 45–58. 
3.  Fogel David B. Using Evolutionary Programming to Schedule Tasks on 
a Suite of Heterogeneous Computers // Computers & Operations re-
search, Vol. 23:6. P. 527–534. 

 
159 

жүктеу/скачать 1,64 Mb.

Достарыңызбен бөлісу: