Python实现简单的遗传算法

硕士毕业论文的时候使用了遗传算法,所以研究了一段时间,曾经用 Python 写一个简单的遗传算法,好自己拿来实验。整个代码还是仿照《游戏编程中的人工智能技术》中的代码来写的。如果想简单的学习一下遗传算法以及简单应用《游戏编程中的人工智能技术》是不错的选择。 代码如下面所附。 我写了一个简单的测试函数 main 运行后多数情况下会产生如下输出 ----------------- Function: y = 0 - 2 * x * x + 12 * x + 5 The best genome is: [0, 0, 1, 1] The variable is: 3 The max value is 23 ----------------- Function: y = 0 - 2 * x * x + 8 * x + 4 The best genome is: [0, 0, 1, 0] The variable is: 2 The max value is 12 ----------------- 以 y = 0 - 2 * x * x + 8 * x + 4 为例,在 Matlab 中画出该函数的曲线的时候,可以看到 该函数的极值点确实在 x = 2 处,证明算法还是相当成功的。 因为写的测试算法主要针对求函数的极大值,如果是求函数极小值可以乘上 -1 就 OK 了。 其实上边的函数,乘上 -1 ,然后求导也可以知道极值为 x=8/4=2 ,这是极小值,乘上 -1 就得极大值了。 算是初步改写成功了,当然还有很多问题,比如选择时用的轮盘赌,但是 AI 的书上的算法似乎有点问题,另外似乎变异操作也有点问题,变异我现在只是变异一处,而原书上则是每一处都根据变异率来进行变异。 种群要设置的稍微大点,太小了没效果。变异率也要大一点。 另外,测试函数里的解空间比较小,还有就是终止条件目前仅判断代数是否超过了设置的最大代数,我想还应该在判断适应性分数最高的地方设置终止条件。这样就避免了多余的运算 [code lang="python"] # -*- coding:utf-8 -*- # file: GA.py # date: 2011-10-22 # note: import random class genome: def __init__(self, length = 0): self.fitness = 0 self.bits = [] for i in range(length): self.bits.append(random.randint(0, 1)) class ga: def __init__(self, pop_size, genome_len, expr = 'y = 0 - 2 * x * x + 8 * x + 4', crossover_rate = 0.7, mutation_rate = 0.01, max_generation = 1000 ): self.crossover_rate = crossover_rate self.mutation_rate = mutation_rate self.pop_size = pop_size self.genome_len = genome_len self.generation = 0 self.genomes = [] self.busy = False self.fittest_genome = genome() self.best_fitness_score = 0 self.total_fitness_score = 0 self.expr = expr self.max_generation = max_generation def create_start_populations(self): del self.genomes[0:] for i in range(self.pop_size): self.genomes.append(genome(self.genome_len)) self.generation = 0 self.best_fitness_score = 0 self.total_fitness_score = 0 def selection(self): f_slice = random.uniform(0, 1) * self.total_fitness_score c_f_slice = 0.0 selected_genome = 0 for i in range(self.pop_size): c_f_slice = c_f_slice + self.genomes[i].fitness if c_f_slice f_slice: selected_genome = i break return self.genomes[i] def crossover(self, mum, dad): baby1 = [] baby2 = [] if (random.uniform(0, 1) self.crossover_rate): baby1 = mum.bits; baby2 = dad.bits; return baby1, baby2 cp = random.randint(0, self.genome_len - 1) for i in range(cp): baby1.append(mum.bits[i]) baby2.append(dad.bits[i]) for i in range(cp, self.genome_len): baby1.append(dad.bits[i]) baby2.append(mum.bits[i]) return baby1, baby2 def mutate(self, bits): if (random.uniform(0, 1) self.mutation_rate): mp = random.randint(0, self.genome_len - 1) bits[mp] = int(not bits[mp]) def decode(self, gen): x = self.bin2int(gen) exec(self.expr) return y def bin2int(self, lists): m = 1 r = 0 lists.reverse() for i in range(len(lists)): r = r + m * lists[i] m = m * 2 lists.reverse() return r def update_fitness_scores(self): self.total_fitness_score = 0 for i in range(self.pop_size): self.genomes[i].fitness = self.decode(self.genomes[i].bits) self.total_fitness_score ...

阅读全文 »

python challenge 20解题总结

 

python challenge 20网址:www.pythonchallenge.com/pc/hex/idiot.html,查看网页源码后,可以看到idiot2.html,于是打开网址:www.pythonchallenge.com/pc/hex/idiot2.html,查看网页的源码就看到了but inspecting it carefully is allowed,于是想到需要用到httplib模块,并且需要用认证的信息,于是源代码如下。

import httplib, base64

base64_login = base64.encodestring('%s:%s' % ("butter", "fly"))[:-1]
headers = {"Authorization": "Basic %s" % base64_login}
conn = httplib.HTTPConnection("www.pythonchallenge.com")

# Needless to say that normally we wouldn't know about the exact byte
# ranges yet and thus probably use infinite loops instead ...

for n in range(30203, 30314):
    headers["Range"] = "bytes=%s-%s" % (n, n + 1)
    conn.request("GET", "/pc/hex/unreal.jpg", "", headers)
    response = conn.getresponse()
    data = response.read()

    if data:
        print data

# We now know that our username is "invader".

for n in (2123456744, 2123456743):
    headers["Range"] = "bytes=%s-%s" % (n, n + 1)
    conn.request("GET", "/pc/hex/unreal.jpg", "", headers)
    response = conn.getresponse()

    print response.read()

# We learned that "the password is your new nickname in reverse", thus:
# "redavni". Further, that "it is hiding at 1152983631".

headers["Range"] = "bytes=1152983631-1152983632"
conn.request("GET", "/pc/hex/unreal.jpg", "", headers)
response = conn.getresponse()

h = open("data.zip", "wb")
h.write(response.read())
h.close()

# Unzip the file and read the "readme.txt" it contains.

阅读全文 »

python challeng 21 解题总结

这一关没有需要进入的网页,但是需要上一关得到一个文件,解析这个文件内容就行了。(用户名: butter; 密码: fly

 

源代码如下:

 

import zlib, bz2

h = open("package.pack") # Hides within the ZIP file we got at the
data = h.read()          # end of level 20.
h.close()

output = []

while True:
    if data.startswith("BZh"):
        data = bz2.decompress(data)
        output.append("#")
    elif data.startswith("xx9c"):
        data = zlib.decompress(data)
        output.append(" ")
    elif data.endswith("x9cx"):
        data = data[::-1]
        output.append("n")
    else:
        break

print "".join(output)

 

 

 

 

 

 

下一关网址:www.pythonchallenge.com/pc/hex/copper.html

 

阅读全文 »

python challeng 22 解题总结

python challenge 22网址:www.pythonchallenge.com/pc/hex/copper.html,查看网页源代码会发现一个提示:maybe white.gif would be more bright,于是打开和下载www.pythonchallenge.com/pc/hex/white.gif,发现这个gif是多帧的,差不多在图像的正中间有比黑色稍微亮一点的颜色……那些颜色出现在小键盘一样布局的3*3的9个位置上。然后一次当作方向向量描点处理.

源代码如下:

 

import Image, ImageSequence

img = Image.open("white.gif") # http://www.pythonchallenge.com/pc/hex/white.gif
out = Image.new("P", (125, 125))
pix = out.load()
pos = [25, 25]

for x in [list(f.getdata()).index(8) for f in ImageSequence.Iterator(img)]:
    if x == 19698:
        pos[0] -= 1
        pos[1] -= 1
    elif x == 19700:
        pos[1] -= 1
    elif x == 19702:
        pos[0] += 1
        pos[1] -= 1
    elif x == 20098:
        pos[0] -= 1
    elif x == 20100:
        pos = [pos[0] + 10, pos[1] + 10]
    elif x == 20102:
        pos[0] += 1
    elif x == 20498:
        pos[0] -= 1
        pos[1] += 1
    elif x == 20500:
        pos[1] += 1
    elif x == 20502:
        pos[0] += 1
        pos[1] += 1

    pix[pos[0], pos[1]] = 200

out.save("solution.png")

 

下一关的网址:www.pythonchallenge.com/pc/hex/bonus.html(用户名:butter,密码:fly)

 

阅读全文 »

python challeng 23 解题总结

python challenge 23网址:www.pythonchallenge.com/pc/hex/bonus.html,查看网页源代码会发现两个提示:(1)this is an undocumented module;(2)va gur snpr bs jung?。由第一个提示就能想到this这个模块,但是第二个提示是进行一些处理过的字符串,如果是使用linux或者unix,就会发现:

grep -i "va gur snpr bs" *
this.py:Va gur snpr bs nzovthvgl, ershfr gur grzcgngvba gb thrff.

换成英文就是:

In the face of ambiguity, refuse the temptation to guess.

于是就得出答案,下一关的网址就是:www.pythonchallenge.com/pc/hex/ambiguity.html(用户名:butter,密码:fly)


阅读全文 »

python challeng 24 解题总结

python challenge 24网址: www.pythonchallenge.com/pc/hex/ambiguity.html ,查看网页源码会得出一个提示:from top to bottom,仔细一看图片:好复杂的一张maze图呀,于是试着下面的方式找到答案。 开始试着以白色为道路非白色为墙壁,用以前写过的A*算法找路径,结果没有路。 又仔细放大图片查看边缘,原来右上角和左下角各有一个黑色像素 这么说就是就是以白色为墙壁非白色为道路了,再次找路,找到。 又没有头绪了,开始猜想也许通路能组成图形字符,结果啥也看不出来。 参考攻略,原来是依次将路径间隔着取所在的像素的r值,存入文件中。 存成的文件是个zip,打开,里面有两个文件maze.jpg和mybroken.zip,其中maze.jpg 打开是个图片,上面有lake字样 == http://www.pythonchallenge.com/pc/hex/lake.html 而mybroken.zip打开里面有个mybroken.gif,不过无法打开,似乎没有用。 源代码如下: def level_24(): class Node: def __init__(self,parent,x,y,h): self.parent=parent self.x,self.y=x,y self.hv = (x 16) ^ y self.g,self.h=0,h def __repr__(self): return '(%d,%d)'%(self.x,self.y) def __eq__(self,other): return self.hv == other def __hash__(self): return self.hv class AStarTest: def __init__(self,map_max_x,map_max_y,map): self.openlist,self.closedlist=[],set() self.mapMaxX,self.mapMaxY=map_max_x,map_max_y print '%d %d'%(self.mapMaxX,self.mapMaxY) self.map=map def inCloseList(self,x,y): u"""检查(x,y)是否在closedlist中""" return (x 16) ^ y in self.closedlist def inOpenList(self,x,y): u"""检查(x,y)是否在openlist中""" for i,n in enumerate(self.openlist): if n.x==x and n.y==y: return i return -1 def showPath(self,l,showmark): u"""显示路径""" tm=[] # 用来保存从起点到终点的路径坐标列表 for i in l: tm.append((i.x,i.y)) if showmark: # 在新图中显示出路径来 f=PngImagePlugin.PngImageFile(r'd:maze.png') my=f.copy() draw=ImageDraw.Draw(my) draw.point(tm,showmark)# (0,0,255,255)) my.save(r'd:maze_showpath.png','png') # 将路径间隔着取像素的r值保存到zip文件中 f=PngImagePlugin.PngImageFile(r'd:maze.png') fo=open(r'd:maze.zip','wb') data=[] for i in tm[1::2]: # 从第二个像素开始间隔着取 r,dummy,dummy,dummy=f.getpixel(i) data.append(r) fo.write(''.join([chr(item) for item in data])) fo.close() def SubNode(self,node,to_x,to_y): u""" 返回节点node的有效子节点""" subList=[ (node.x,node.y-1), (node.x-1,node.y), (node.x+1,node.y), (node.x,node.y+1), ] for x,y in subList: if self.map[y][x] !='#': # 坐标值有效 if not self.inCloseList(x,y): # 不在closedlist中 item= Node(node,x,y,sqrt((x-to_x)*(x-to_x)+(y-to_y)*(y-to_y))*1.2) item.g=item.parent.g+1.0 yield item def getPath(self,from_x,from_y,to_x,to_y,show_mark=None): u"""获取两点间的路径 from_coord 起点 to_coord 终点 show_mark 用来显示路径的颜色 """ print "(%d,%d)- (%d,%d)"%(from_x,from_y,to_x,to_y) self.openlist.append(Node(None,from_x,from_y,0)) while self.openlist: # 重复如下的工作: # a) 寻找开启列表中F值最低的格子。我们称它为当前格。 minf,minidx,curCoord=1000000,-1,None # 假设当前最新f为1000000 for i,n in enumerate(self.openlist): if n.g+n.h minf: minf=n.g+n.h curCoord=n minidx=i # b) 把它切换到关闭列表。 del self.openlist[minidx] self.closedlist.add(curCoord) # c) 对相邻的8格中的每一个 for item in self.SubNode(curCoord,to_x,to_y): # 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。 # 记录这一格的F,G,和H值。 i=self.inOpenList(item.x,item.y) if i==-1: self.openlist.append(item) # 保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。 if item.x==to_x and item.y==to_y: print "found %d,len(closedlist)=%d"%(item.g,len(self.closedlist)) l=[item] p=item.parent while p: l.append(p) p=p.parent l.reverse() self.showPath(l,show_mark) return True # 如果它已经在开启 ...

阅读全文 »

python challeng 25 解题总结

 python challenge 25网址:www.pythonchallenge.com/pc/hex/lake.html(用户名:butter,密码:fly)。查看网页源代码可以看到一个提示:can you see the waves。于是想到去看网址:www.pythonchallenge.com/pc/hex/lake1.wav,果然存在这个音频文件,看到关数以及拼板的数量,于是一直下载到lake25.wav.这是一个奇怪的帧率音频文件。让我们的波形编辑器打开它,看看它是什么样子。嗯,有一个明确的行为期3样本,而不是我们期望在所有的音频。也许它并不是在所有的音频,但一些其他形式的数据编码,说一个形象,一个拼图的一部分。如果我们除以3(3个字节,每个像素),我们得到完整的拼图3600。

源代码如下:

 

 

 

##	template = "http://butter:fly@www.pythonchallenge.com/pc/hex/lake%i.wav"
##	fname=r'd:25_lake%d.wav'
##	for i in range(1, 26):
##		urllib.urlretrieve(template % i,fname%i)
##	# 完成拼接
##	l=[]
##	for i in range(1,26):
##		f=wave.open(ur'd:25_lake%d.wav'%i,'rb')
##		l.append(f.readframes(f.getnframes()))
##		f.close()
##	im=Image.new('RGB',(300,300))
##	for i in range(25):
##		im.paste(Image.fromstring('RGB',(60,60),l[i]),( 60*(i%5),60*(i//5)))
##	im.show()

 

 

下一关网址:www.pythonchallenge.com/pc/hex/decent.html

阅读全文 »

python challenge 26解题总结

python challenge 26网址:www.pythonchallenge.com/pc/hex/decent.html(需要用户名和密码的话,用户名为butter,密码为fly),查看网页源代码以及图片会发现:

# be a man - apologize!
# 图中是抓耳挠腮的猴子,下面有句话 Hurry up, I'm missing the boat
# 网页注释中有 <!-- you've got his e-mail -->
# 联想到前面第19关解一个邮件里面的音频文件,当时没有记那个email地址
# 回去找,是 leopold.moz@pythonchallenge.com
# 发封邮件到这个地址,既然要道歉,就说sorry吧
# 得到如下输出
# 发件人    Leopold Mozart <leopold.moz@pythonchallenge.com>
# 发送至    keep.studying.everyday@gmail.com
# 日期    2010年1月5日 下午11:58
# 主题    Re: my broken zip Re: sorry
# 邮送域    mail-yw0-f121.google.com
#
# Never mind that.
#
# Have you found my broken zip?
#
# md5: bbb8b499a0eef99b52c7f13f4e78c24b
#
# Can you believe what one mistake can lead to?

# 这让我想到第24关的那个mybroken.zip
# 看来要想办法根据md5修复这个zip文件
# 用winrar修复失败
# 又没有思路了。。。
# 看攻略的解法:
# 信中的最后一句意思是你能相信错了一个字节就会出现这个吗?暗示你那个zip文件有一个字节错了。
# 所以修复方法是,枚举每个字节的所有可能值,然后算md5,直到与已知的正确md5值相同为止。
# 从修复好的zip文件里打开gif文件,里面显示 speed  ==> http://www.pythonchallenge.com/pc/hex/speed.html
# 地址不对
# 猜吧,发现正确的是speedboat ==> http://www.pythonchallenge.com/pc/hex/speedboat.html

源代码如下:

def level_26():
  data=open(ur'd:mybroken.zip','rb').read()
  for i in range(len(data)):
    for c in range(256):
      newdata=data[:i]+chr(c)+data[i+1:]
      if hashlib.md5(newdata).hexdigest()=='bbb8b499a0eef99b52c7f13f4e78c24b':
        open(ur'd:mybroken_repaired.zip','wb').write(newdata) # 修复好的文件打开里面的mybroken.gif, 图中显示 speed
        print 'repaired.'
        return

下一关网址:www.pythonchallenge.com/pc/hex/speedboat.html(用户名:butter,密码:fly)

 

阅读全文 »

python challenge 27 解题总结

这一关是参照别人的方法做的,方法如下: A picture showing an oar with a zigzag line. Title between the tables , clues did you say gif? and oh, and this is NOT a repeat of 14 . There s a link to bell [ that s level 28 ] but that s password protected; the login domain is the order matters . Trying zigzag.gif as suggested, I see that the GIF is interlaced, which is new. Is that significant? [ No, it s not. ] It s a greyscale image with 256 levels of grey in the pixels, no clear pattern: zig = get_image('hex/zigzag.gif') zigdata = zig.tostring() hex(zigdata[:20]) 'd7d0cb0cfe266c743b8b4842bd7fb0ad46aacf27207e8e' The reference to level 14 suggests that spiral order is not it (and if it were, the opening bytes d7 d0 cb don t suggest any file format). So what about zigzag order? I can t find any place to start that looks like the beginning of a file. What about the palette? It appears to have each colour in it once: len(zig.getcolors()) 256 palette = zig.palette.getdata()[1][::3] # 3 bytes per pixel, equal RGB hex(palette[:20]) '25e5a2883bd40929189c9470fe5b6a31f8d5dc0f' The values in the image data are the numbers of palette entries. What if we translate the image data by the palette, getting greyscale values? t = string.maketrans(''.join([chr(i) for i in range(256)]), palette) zigtrans = zigdata.translate(t) hex(zigtrans[:20]) 'd0cb0cfe266c743b8b4842bd7fb0ad46aacf27207e8ea4' Still nothing. Hang on, isn t that very similar to the original data? It s identical, except that it s missing the first byte. Is it identical all the way to the end? zigdata[1:] == zigtrans[:-1] False What if we gather up all the bytes which are different in the two strings? deltas = filter(lambda p: p[0] != p[1], zip(zigdata[1:], zigtrans[:-1])) diffs = [''.join([p[i] for p in deltas]) for i in range(2)] diffs[0][:20] 'BZh91AY SYxe0xaaYFx00x17x9ax11x80@' diffs[1][:20] '99bd5182f289530415450437200495e44e9bd5a8' On the one side, a bzip2-compressed datastream, on the other, what? I don't recognize it. bz = bz2.BZ2Decompressor().decompress(diffs[0]) len(bz) 70644 bz[:100] '../ring/bell.html del assert repeat raise or class is exec return except print return switch from ex' It s a bunch of Python keywords plus ../ring/bell.html . Let s see how many and what they are. keywords = bz.split(' ') keys = {} for k in keywords: keys[k] = 1 ... keys.keys() ['and', 'elif', 'is', 'global', 'in', 'if', 'from', 'raise', 'for', 'except', 'switch', 'finally', 'print', 'import', 'pass', 'repeat', 'return', 'exec', 'else', 'assert', 'not', 'class', '../ring/bell.html', 'yield', 'try', 'while', 'continue', 'del', 'break', 'or', 'def', 'lambda'] len(keywords) 12000 len(keys.keys()) 32 12000 / 32 375 Are we meant to apply the same technique to this datastream? But if so, where s the table? Does this datastream code for an image? (I tried several plausible ideas, but it looks like random noise each time.) Finally, in desperation, I tried every possible pair of keywords as username and password: auth_handler = ...

阅读全文 »

python challenge 28解题总结

python challenge 28网址:www.pythonchallenge.com/pc/ring/bell.html用户名是repeat 密码是 switch

  • 图片是瀑布,湖,丛林,图片上面似乎覆盖着很多长短不一的竖条
  • many pairs ring-ring
  • 提示 RING-RING-RING say it out loud
  • 再次失去思路
  • 一个攻略说,传说中ring-ring-ring 反复读会变成green
  • 另一个则说,会变成grin
  • 先看grin  ==> http://www.pythonchallenge.com/pc/ring/grin.html
  • 网页上提示 you are not happy - you are feeling sick.
  • 再看green ==> http://www.pythonchallenge.com/pc/ring/green.html
  • 网页上提示 yes! green!
  • 解码图片上短竖条中的g值

源代码:

 

def level_28():
	im=PngImagePlugin.PngImageFile(ur'd:bell.png')
	l=[]
	for y in range(im.size[1]):
		for x in range(im.size[0]):
			l.append(im.getpixel((x,y))[1])
	print l[:10]
	paris=[(l[i],l[i+1]) for i in range(0,len(l),2)] # 根据"my paris" 将像素两两分为一组
	# 可以看出基本上每个paris内两像素之差都为42
	print paris[:10]

	diffs=[abs(i[0]-i[1]) for i in paris] # 计算两两像素之差的绝对值
	print diffs[:10]

	d=[x for x in diffs if x!=42] # 过滤掉差值等于42的
	print d

	s=''.join([chr(x) for x in d])  # 剩下的差值转为字符
	print s # 输出 whodunnit().split()[0] ?

	# 到此就有些让我奇怪了,whodunnit是到结尾才知道谋杀犯的侦探小说的意思,怎么会联想到Python发明人Guido Van Rossum ?
	# 难道是发音像 who done it 谁做了这些
	print 'Guido Van Rossum'.split()[0] # 输出 guido  ==> http://www.pythonchallenge.com/pc/ring/guido.html

	# 从官方wiki看到获取所有像素的g值的更好方法是
##	im=Image.open(ur'd:bell.png')
##	green=im.split()[1]
##	greendata=green.getdata()

 

下一关的网址:www.pythonchallenge.com/pc/ring/guido.html用户名是repeat 密码是 switch

 

阅读全文 »