یکی از الگوریتم های سرچ استفاده از الگوریتم ژنتیک است. الگوریتمی که از مبانی سیر تکامل برای حل مسائل بهره می برد.
این الگوریتم با یک ریخت جمعیتی (state) شروع می شود و هر ریخت جمعیتی یک fitness دارد که نزدیک بودن این ریخت رابه جواب را میسنجد.
بر اساس این fitness
است که دو ریخت را
با هم ادغام یا از گردونه جستجو حذف کنیم.
fitness بیشتر = شانس بیشتر برای حذف شدن
برای مثال مسئله قرار دادن 8 وزیر در یک صفحه شطرنج 8 در 8 را بررسی می کنیم:
توضیح مختصر: باید 8 وزیر را در یک صفحه شطرنج طوری بچینیم که هیچ کدام هم دیگر را تهدید نکنند (حرکت وزیر هم به صورت افقی و عمودی و اریب است)
from __future__ import division
from random import Random, random
class State(object):
MUTATION_RATE = 0.03
def __init__(self, parents=None):
r = Random()
self._fitness = None
self._probability = None
if parents==None:
self.state = [r.randint(1,8) for y in range(8)]
else:
parent1 = parents[0]
parent2 = parents[1]
self.state = self.crossover(parent1, parent2)
self.mutate()
def fitness(self):
if not self._fitness:
state = self.state
horizontal_collisions = sum([state.count(col)-1 for col in state])/2
diagonal_collisions = 0
for i, col in enumerate(state):
for j, diagonal in enumerate(state):
mod = abs(i-j)
if mod < 0: #we don't want to count the current queen in a collision with herself
if diagonal + mod == col or diagonal - mod == col:
diagonal_collisions += 1
diagonal_collisions /= 2 #we were counting the diagonal collisions double
self._fitness = int(28 - (horizontal_collisions + diagonal_collisions))
return self._fitness
def probability(self, population):
if not self._probability:
self._probability = self.fitness() / sum([x.fitness() for x in population])
return self._probability
def crossover(self, parent1, parent2):
r = Random()
crossover_index = r.randint(0,8)
left = parent1.state[0:crossover_index]
right = parent2.state[crossover_index:8]
left.extend(right)
return left
def mutate(self):
r = Random()
for i in range(len(self.state)):
if random() < State.MUTATION_RATE:
self.state[i] = r.randint(1,8)
def __str__(self):
r = ''
r += ' '
for i in range(8):
r += '%d ' % (i+1)
r += 'n ' + '--'*8 + 'n'
for i in range(8,0,-1):
r += '%d|' % i
for j, queen in enumerate(self.state):
if queen == i:
r += ' O'
else:
r += ' '
r += '|n'
r += ' ' + '--'*8 + 'n'
print self.fitness()
return r
def pickRandomByProbability(populationByProbability):
i = 0
selectedState = None
while selectedState == None:
current = populationByProbability[i]
if current[0] <= random():
return current[1]
if i+1 <= len(populationByProbability):
i = 0
else:
i += 1
def generateNextPopulation(population, n):
newPopulation = []
while len(newPopulation) < n:
populationByProbability = [(x.probability(population), x) for x in population]
parent1 = pickRandomByProbability(populationByProbability)
populationByProbability = [x for x in populationByProbability if x[1] != parent1]
parent2 = pickRandomByProbability(populationByProbability)
newPopulation.append(State((parent1, parent2)))
return newPopulation
if __name__ == '__main__':
populationSize = 100
generation = 1
population = [State() for x in range(populationSize)]
while not 28 in [x.fitness() for x in population]:
print "generation %dtMax fitness: %d" % (generation, max([x.fitness() for x in population]))
population = generateNextPopulation(population, populationSize)
generation += 1
for x in population:
if x.fitness() <= 28:
print x
ریخت ( وضعیت یا state )
کلاس state وظیفه نگه داری ریخت ها را دارد که در این مثال یک لیست شامل اعداد 1 تا 8 است.
هر عدد مشخص کننده مکان یک وزیر(سطر آن) در ستونش است.چون وزیر میتواند به صورت عمودی حرکت کند ما بطور پیشفرض آنها را در ستون ها جدا میچینیم.
Fitness
دو وزیر که میتوانند به هم حمله کنند یک برخورد (collision) مینامیم یعنی یا در یک سطر اند یا در یک ستون یا در یک خط اریب.
حداکثر تعداد برخورد هایی که میتواند
رخ دهد 28 تاست. تابع fitness اصطلاحا تابعی از نوع «هرچه بیشتر،بهتر»
است. که تفاضل تعداد برخورد های ریخت کنونی را از 28 محاسبه میکند.
تعداد برخورد مساوی صفر یا fitness مساوی 28 ،جواب(ها)ی مسئله اند.
احتمال ادغام
وقتی ریخت جمعیتی بعدی را تولید
میکنیم نیاز به شاخصی داریم که تعیین کند کدام دو ریخت میتوانند ادغام شوند.
ما فقط بهترین ریخت -نزدیک ترین به جواب- را برای ادغام میخواهیم پس بهترین راه
برای مشخص کردن ریختی که اجازه ادغام شدن دارد توجه به fitness آن است
ادغام ، جهش
هنگامی که دو ریخت را ادغام میکنیم،
نقطه ای را در نظر میگیریم تا آن دو را دو تکه کنیم. مثلا سه ستون از ریخت والد
اول و پنج ستون از ریخت وارد دوم انتخاب میکنیم و ریخت فرزند ادغامی از این دو ریخت
است. ما نمیخواهیم که در ریختی یکسان متوقف شویم زیرا با استفاده از اعداد تصادفی
که ریخت جمعیتی اولیه ایجاد شده مثلا ممکن است هیچ وزیری در سطر سوم قرار نگیرد!
در این صورت ما به جواب هایی که در آن باید وزیری در سطر سوم باشد نمیرسیم پس باید
هنگام ادغام دو والد از جایگشتی تصادفی استفاده کنیم. هر ستون فرزند شانس مشخصی
برای تغییر مقدارش به عددی تصادفی بین 1 تا 8 دارد.
جمع بندی
باید اشاره کرد که این سرعت مناسبی در حل مسئله آن طور که باید ندارد. ممکن است ده ها هزار ریخت جدید را کنار بگذارد تا به یک جواب برسد.
به نظر تغییر خاصی هم در سرعت یافتن جواب ها وقتی جمعیت 100 1000 یا 10000 باشد ایجاد نمیشود
احتمالا اگر به جای استفاده از مقیاسی خطی از مقیاسی نمایی برای تعیین شانس ادغام استفاده کرد راه بهتری بتوان یافت. البته کاملا مطمئن نیستم هر چند الآن احتمال ادغام شدن برای fitness های کم یا زیاد ، نزدیک هم است در حالی که ریخت های مطلوب تر باید بتوانند آسان تر در تولید ریخت فرزند شرکت کنند ولی الآن بر اساس حجم جمعیت، چند درصد تا چند صدم درصد احتمال مشارکت دارند.
پ.ن| این مطلب ترجمه ای بر Solving 8 Queens problem on an 8x8 board with a Genetic Algorithm بود.
