3.3.1 Класс floatbee

Это базовый класс, от которого необходимо наследоваться и переопределить один метод, также в конструкторе нужно определить некоторые объекты. А именно: self.position, self.minval, self.maxval.

Эти переменные должны быть типа список (или массив) и содержать столько элементов, сколько аргументов имеет целевая функция, которую необходимо оптимизировать.

self.position хранит в себе одно решение, которое сопоставлено с данной пчелой. В конструкторе рекомендуется заполнять этот список случайными величинами.

self.minval и self.maxval хранят списки, содержащие соответственно минимальные и максимальные значения для координат из self.position.

Допустим, что положение определяется двумя координатами, причем первая координата может изменяться в пределах [-1; 1], а вторая в пределах [-11; 12]. Тогда заполнение этих выглядит следующим образом:

self.minval = [-1.0, -11.0]

self.maxval = [1.0, 12.0]

self.position = [random.uniform (self.minval[n], self.maxval[n]) for n in range(2)]

Таким образом, размеры списков self.position, self.minval и self.maxval всегда должны совпадать.

После заполнение списков, необходимо перегрузить метод def calcfitness (self).

Именно в нем рассчитывается целевая функция. Следует особо отметить, что само значение целевой функции не возвращается из этого метода, а присваивается внутри метода переменной self.fitness. Сам метод ничего не возвращает.

Это сделано для того, чтобы целевая функция считалась только один раз при изменении координат пчелы. Причем метод calcfitness() должен быть обязательно выполнен после любых перемещений пчелы.

Рассмотрим пример. Пусть целевая функция имеет вид:

Тогда метод calcfitness()выглядит следующим образом:

class mybee (pybee.floatbee):

def calcfitness (self):

self.fitness = 0.0

for val in self.position:

self.fitness -= val * val

Соответственно, конструктор будет выглядеть следующим образом:

class mybee (pybee.floatbee):

def __init__ (self):

self.minval = [-1.0, -11.0]

self.maxval = [1.0, 12.0]

self.position = [random.uniform (self.minval[n], self.maxval[n]) for n in range(2) ]

self.calcfitness()

3.3.2 Класс hive

Основные шаги алгоритма роя пчел реализованы внутри класса hive(улей).

Рассмотрим параметры конструктора.

class hive:

def __init__ (self, scoutbeecount, selectedbeecount, bestbeecount, selsitescount, bestsitescount, range_list, beetype):

В конструктор передаются следующие параметры:

1) scoutbeecount - количество пчел-разведчиков.

2) selectedbeecount - количество пчел, посылаемых на каждый из выбранных (не лучших) участков. Сколько пчел отправляется на один участок.

3) bestbeecount - количество пчел, посылаемых на каждый из лучших участков.

4) selsitescount - количество выбранных перспективных участков.

5) bestsitescount - количество лучших участков.

6) range_list - список, элементы которого определяют размеры выбранных и лучших участков по каждой координате.

7) beetype - класс пчел, производный от floatbee, который используется в алгоритме.

Параметр range_list представляет собой список размеров областей, куда отправляются пчелы. Его роль в алгоритме продемонстрируем на примере.

Пусть положение участков определяется двумя координатами (целевая функция имеет два параметра), тогда список (или массив) range_list имеет два элемента. Пусть это будут [1,0; 2,0].

Это значит, что при отправке пчелы в область какой-то точки (x;y), значение ее первой координаты будет случайным образом выбрано из интервала [x-1,0; x+1,0], а значение второй координаты - [y-2,0; y+2,0]. То есть, если мы отправим пчелу в область точки (10,0; 20,0), то в реальности получим координаты, которые будут лежать в пределах от 9,0 до 11,0 для первой координаты и от 18,0 до 22,0 для второй.

Для отправки пчелы в окрестность точки в классе floatbee есть метод def goto (self, otherpos, range_list)в котором

otherpos - точка, в окрестность которой посылается пчела,

range_list - тот же самый список размеров окрестностей.

Конструктор класса hive.

class hive:

def __init__ (self, scoutbeecount, selectedbeecount, bestbeecount, \

selsitescount, bestsitescount, \

range_list, beetype):

self.scoutbeecount = scoutbeecount

self.selectedbeecount = selectedbeecount

self.bestbeecount = bestbeecount

self.selsitescount = selsitescount

self.bestsitescount = bestsitescount

self.beetype = beetype

self.range = range_list

self.bestposition = None

self.bestfitness = -1.0e9

beecount = scoutbeecount + selectedbeecount * selsitescount + bestbeecount * bestsitescount

self.swarm = [beetype() for n in xrange (beecount)]

self.bestsites = []

self.selsites = []

self.swarm.sort (floatbee.sort, reverse = True)

self.bestposition = self.swarm[0].getposition()

self.bestfitness = self.swarm[0].fitness

В нем сохраняются все передаваемые параметры. А также создается переменная self.bestposition, которая хранит в себе лучшее на данный момент решение.

Значение целевой функции для лучшего на данный момент решения хранится в переменной self.bestfitness.

Затем создается рой пчел. Общее количество пчел в нем равно

beecount = scoutbeecount + selectedbeecount * selsitescount + bestbeecount * bestsitescount

Затем заполняется список переменной self.swarm (рой):

self.swarm = [beetype() for n in xrange (beecount)]

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

После того как рой создан, он сортируется по убыванию целевой функции у каждой пчелы. В качестве функции сравнения передается метод sort() из класса floatbee.

После сортировки лучшим будет решение у пчелы, находящейся в самом начале списка. Значение целевой функции для данной пчелы сохраняется в переменной self.bestfitness, а в переменной self.bestposition сохраняется копия координат лучшей пчелы. Для получения копии координат используется метод getposition() из класса floatbee:

class floatbee:

def getposition (self):

return [val for val in self.position]

Для выполнения одной итерации алгоритма роя пчел необходимо из экземпляра класса hive вызвать метод def nextstep (self).

Метод def nextstep (self)состоит из двух логических этапов. Сначала выбираются лучшие и выбранные участки. Выбор лучших участков происходит следующим образом:

class hive:

def nextstep (self):

self.bestsites = [ self.swarm[0] ]

curr_index = 1

for currbee in self.swarm [curr_index: -1]:

if currbee.otherpatch (self.bestsites, self.range):

self.bestsites.append (currbee)

if len (self.bestsites) == self.bestsitescount:

break

curr_index += 1

Пчелы, нашедшие лучшие участки помещаются в список self.bestsites. Туда помещается пчела, находящаяся в начале списка, а затем происходит перебор остальных пчел до тех пор пока не будет отобрано нужное количество. Причем пропускаются пчелы, которые находятся в одном участке с пчелой, которая уже находится в списке self.bestsites. Переменная curr_index хранит номер пчелы в списке, которая проверятся следующей.

Проверка того является ли участок, найденный пчелой новым или какая-то пчела уже находится поблизости, происходит внутри метода otherpatch() класса floatbee.:

class floatbee:

def otherpatch (self, bee_list, range_list):

if len (bee_list) == 0:

return True

for curr_bee in bee_list:

position = curr_bee.getposition()

for n in xrange ( len (self.position) ):

if abs (self.position[n] - position[n]) > range_list[n]:

return True

return False

В данном случае в качестве bee_list передается список лучших пчел self.bestsites, а в качестве range_list все тот же список размеров окрестностей. Участок, найденный пчелой, считается новым, если в списке bee_list нет пчелы, расстояние до которой по каждой из координат не превышает соответствующего размера из range_list.

После нахождения лучших участков аналогично выделяем выбранные участки:

class hive:

def nextstep (self):

self.selsites = []

for currbee in self.swarm [curr_index: -1]:

if currbee.otherpatch (self.bestsites, self.range) and currbee.otherpatch (self.selsites, self.range):

self.selsites.append (currbee)

if len (self.selsites) == self.selsitescount:

break

Пчелы с выбранных участков сохраняются в список self.selsites.

Затем, отправляем пчел на соответствующие позиции:

class hive:

def nextstep (self):

bee_index = 1

for best_bee in self.bestsites:

bee_index = self.sendbees (best_bee.getposition(), bee_index, self.bestbeecount)

for sel_bee in self.selsites:

bee_index = self.sendbees (sel_bee.getposition(), bee_index, self.selectedbeecount)

for curr_bee in self.swarm[bee_index: -1]:

curr_bee.gotorandom()

self.swarm.sort (floatbee.sort, reverse = True)

self.bestposition = self.swarm[0].getposition()

self.bestfitness = self.swarm[0].fitness

За отправку пчел отвечает метод sendbees() класса hive. Внутри метода sendbees() вызывается метод goto() класса floatbee:

class floatbee:

def goto (self, otherpos, range_list):

self.position = [otherpos[n] + random.uniform (-range_list[n], range_list[n]) \for n in xrange (len (otherpos) ) ]

self.checkposition()

self.calcfitness()

Здесь заполняется список новых координат, которые складываются из точки, в которую отправляют пчелу и случайной величины в интервале от -range_list[n] до range_list[n].

Затем вызывается метод checkposition(), который корректирует координаты, если они выходят за заданные пределы (minval и maxval)

class floatbee:

def checkposition (self):

for n in range ( len (self.position) ):

if self.position[n] < self.minval[n]:

self.position[n] = self.minval[n]

elif self.position[n] > self.maxval[n]:

self.position[n] = self.maxval[n]

После того как были отправлены пчелы на лучшие и выбранные места, оставшихся пчел из улея отправляем на случайные координаты. Затем все пчелы опять сортируются по убыванию целевой функции и сохраняются лучшие позиции и лучшее значение целевой функции.

Метод nextstep() вызывается пользователем до тех пор, пока не будет выполнено одно из условий останова.

3.3.3 Класс statistic

В модуле pybee есть еще один класс, который не используется в алгоритме непосредственно, но который может помочь в отладке и визуализации результатов. Это класс statistic, который сохраняет найденное решение для каждого шага итерации. Причем, один экземпляр класса statistic можно использовать для нескольких независимых запусков алгоритма. Это может понадобиться для того, чтобы посмотреть, например, как сходятся параметры при усреднении по нескольким запускам.

Рассмотрим конструктор класса statistic.

class statistic:

def __init__ (self):

self.fitness = []

self.positions = []

self.range = []

В классе содержатся три списка, которые хранят значения целевой функции, координат и размеров областей. Хранятся значения следующим образом. self.positions хранит список, первый индекс которого обозначает номер запуска алгоритма. Внутри каждого элемента хранится список, каждый элемент которого обозначает номер итерации алгоритма. А внутри этого второго списка хранится список координат, лучших на данную итерацию. То есть, чтобы получить k-ую координату, которая была при m-ой итерации при n-ом запуске алгоритма, необходимо написать следующее выражение stat.positions[n][m][k].

Аналогично со списком range.

Для каждой итерации алгоритма (после каждого вызова метода nextstep() класса hive) необходимо вызвывать метод add(), который добавляет результат в статистику: def add (self, runnumber, currhive).

3.4 Выводы