用遗传算法求复杂函数的极值点

2013年4月17日 23:15

之前也接触过遗传算法，只是没有实践，正巧这次模式识别的课程上老师提到，并布置了一个小练习题，便拿来做做吧。

题目本来要求是求Rosenbrock函数f(x, y) = (x-1)2 + 100(y-x2)2在[-2,-2,2,2]之间的最大值，稍加分析，或者看下面的图就会发现，其实当(x, y) = (-2, -2)时，f(x,y)即可取到最大值。

觉得这样没什么意思，于是自己稍微把题目改了下，把x，y都变成sin x，sin y，函数就变成f(x, y) = (sin x-1)2 + 100(sin y-sin2x)2

 

这是一个很漂亮的双峰函数。下面我们来讨论如何用遗传算法来求这个函数的极大值。

编码方式

由于x,y的范围都是[-2,2]，那么可以考虑使用11个二进制的定点小数来编码0.000到2.047这2048个定点小数。在加上1个二进制位符号为，即可表示[-2.047, 2.047]，刚好可以覆盖[-2,2]并且精度为0.001。x和y都采用相同的方法编码，然后拼接在一起，形成一个24位的二进制整数。实现过程中可以使用整数保存，位运算做遗传和变异。

原始个体生成方式

根据编码方式，每一个个体可以用24个二进制位表示，于是可以很简单的随机生成一个[0,1<<24)的整数表示一个个体。生成30个祖先个体

确定遗传、变异方式

遗传方式：任取两个个体(A,B)进行交配，生成两个子个体(C,D)。C基因序列的低k个二进制位来自于A，高24-k个二进制位来自于另一个父本B，其中0<k<24。D基因序列和C的情况真好相反，其低k个二进制位来自于B，高24-k个二进制位来自于A。用python语言表示为

?
1
2
3
4
k = randint(1, 23)
mask = (1<<k) - 1
C = A & mask | B & ~mask
D = B & mask | A & ~mask

变异方式：随机选取24个二进制位中的某一个，如果该位0变成则变成1，否则变成0

确定遗传

在元素个体，遗传得到的个体和变异个体中选取最好的30个个体(对应的函数值最大的30个个体)作为下一次迭代的父样本。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from random import randint
from numpy import sin
 
def decode(g):
    return [((g&0xfff) - 2048) * 0.001, ((g>>12) - 2048) * 0.001]
 
def function_g(g):
    x = decode(g)
    return function(x[0], x[1])
     
def function(x, y):
    return 100 * (sin(x) ** 2 - sin(y)) ** 2 + (1 - sin(x)) ** 2
 
def cmp(g1, g2):
    key = function_g(g1) - function_g(g2)
    if key > 0: return 1
    elif key < 0: return -1
    else: return 0
 
def GA(num = 30, round = 10):
    gene = [randint(0, (1<<24) - 1) for i in range(num)]
    rnd = 0
    while rnd < round:
        rnd += 1
        gene_c = [g ^ (1<<randint(0, 23))  for g in gene]
        gene_h = []
        for g1 in gene:
            for g2 in gene:
                mask = (1<<randint(1, 23)) - 1
                gene_h.append(g2 & ~mask | g1 & mask)
                gene_h.append(g1 & ~mask | g2 & mask)
        gene_tot = gene + gene_h + gene_c
        gene_tot.sort(cmp = cmp, reverse = True)
        gene = gene_tot[:num]
        print "round", rnd, ":", decode(gene[0]), function_g(gene[0])
    return decode(gene[0]) + [function_g(gene[0])]
     
if __name__ == '__main__':
    print GA(30, 10),
结果

经过10得到如下结果， 每一行的三个数字分别对应x, y, f(x, y)

?
1
2
3
4
5
6
7
8
9
10
round 1 : [1.571, -1.464] 397.724305554
round 2 : [1.571, -1.539] 399.797824716
round 3 : [-1.605, -1.548] 403.426161017
round 4 : [-1.605, -1.556] 403.486264841
round 5 : [-1.541, -1.591] 403.561685598
round 6 : [-1.541, -1.575] 403.639747518
round 7 : [-1.573, -1.579] 403.984587994
round 8 : [-1.573, -1.571] 403.998039526
round 9 : [-1.569, -1.571] 403.998694536
round 10 : [-1.569, -1.571] 403.998694536

 

可以看到，结果收敛得非常快，并且经过10次迭代，结果基本稳定。

 

Posted by xhSong Filed in 折腾 Tagged by python 算法 Matplotlib 遗传 Comments[25]

百度之星2012-2013成绩抓取python脚本

2013年1月10日 10:28

这段时间的百度之星又错过了。老了，也做不动了，第二次题目a了一个，第二个一个dp的题目感觉方法对的，可硬是没有调过，看来真的是更不行了。

对于今年的Astar我就不吐槽了。查成绩有点麻烦，翻页翻到手抽筋，写一python脚本，把抓出来的成绩贴贴吧里面，结果被删贴，贴脚本也被删贴，郁闷！

还是把程序贴这里吧

 

总结一下，现在接触过下面这些python库了

  • PIL(Python Imaging Lib)/Image： 图像处理的库

  • cv/cv2：计算机视觉

  • numpy：NumPy is the fundamental package for scientific computing with Python

  • math：数学库

  • csv：csv文件处理

  • MySQLdb：链接mysql数据库

  • mlpy：机器学习库

  • matplotlib：It provides both a very quick way to visualize data from Python and publication-quality figures in many formats. 像matlab那么，可以画出很漂亮的图

  • M2Crypto、Crypto、pyecc：密码学库（hash，对称加密算法，非对称加密算法，签名认证等）

  • webpy：构建一个轻量级网站A minimalist web framework written in Python

  • urllib/urllib2：url访问，页面抓取等

  • re：正则表达式处理

  • os、sys：顾名思义，就是系统、文件的一些操作

  • ConfigParser：配置文件处理

  • Tkinter：图形界面库

python的各种库还是很强大的，o(∩∩)o...哈哈

Posted by xhSong Filed in python Tagged by python 库 百度之星 成绩 Comments[3]

01图

2012年11月03日 19:12

事情很多，就是不想干。之前看到贴吧上一些帖子用字符做画，感觉挺好玩的。于是试着用python写一个用0和1以及作画的程序。先上几个作品吧！

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
            01                                                             
           01  1111111111111                                               
       11111   1111111    11111                                            
     0 111111 111111111   11111 1                                          
   1  1111111111111111111111111   1                                        
  0 11111111111111111111111111111110                                       
 1111  111111111 1 111111111111111111                                      
 1 1    111111    1111111111111111111                                      
011111111111111111111111111    1111111                                     
111111111111111111111111111   111111                                       
  111111111111111111111111111111111                                        
  111111111111    11111111111111   111                                     
 11111111111111  11111111111  1                                            
111      111111 1111110          111111111                                 
1111   11111 1   11  1          11111111111    11111111111       1111      
 1111111111 1      0           1111111111111               1  11111111111  
 1  1               11         1111111111                    1111111111111 
                     11         111111                         11111111111 
       0             1 1           1                            1111111111 
      01 0            0 0         1                              11111111  
     01 01             1        0 11111                           1        
      11 1             1 0     1 111111           1111111          1       
   0    1               1 1   1    1              11111111         1       
        1               11   0                       01111          1      
                        11100       111 1111                        1      
                  1 10111 111                                        1     
                    00101  1                                         1     
                          1                                          1     
                          1                                          1     
                          1                                  1 1     1     
                          1                                1  1      011   
                          1                               1110      11     
                          1                                         1      
                           1                                       1       1
                            0                                     1        
                              11                               11          
                                  011                    1111              
                                           1111111101

源图片：

萌1

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
                               1111             1111                           
          00000000000001 11                            11100000000000001       
       1000000000000001                                     10000000000000     
       0000000000000                                          1000000000000    
      10000000001                                                10000000001   
      100000000                                                    100000001   
       000000                                                        100000    
        001                                                            000     
         1                                                              0      
       00000000000000000000001                      0000000000000000000000     
      100000001        1000000001               0000000001        1100000001   
     0000001              100000000           100000001               0000001  
    000000        11110       0000001        0000001      011011       100000  
   100000   111     001        0000001      0000001       1001     111  100001 
   00000011                 100000000       1000000011                 1000000 
  1000000              0000000000001         10000000000001             1000000
 100000000        1000000000001                   1000000000001        000000001
 10000000001   100000000001                            00000000001    1000000000
 000000000000000000001                                     110000000000000000000
 000000000000000001                                            10000000000000000
10000000000001                                                     1000000000000
11  100000                                                             100001  1
 1                                                                             0
 11                                                                            1
  0                                                                           1
  11                                                                         11
                                                                             1 
    11                                                                      1  
      0                                                                    0   
       11                                                                 1    
          1                                                            10      
           10                                                         1        
              11                                                   1           
                 111                                            11             
                      1111                                111                  
                              1000011111111111111111100000

源图片：

萌2

原理很简单，也没有什么技术含量，就是那个图片变换一下，定两个0和1的阀值，然后就ok了。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/python
# coding=utf-8
from Tkinter import *
from FileDialog import *
import Image
 
file_name = 'a.jpg'
 
def getFileName():
    file_dialog = LoadFileDialog(frame)
    global file_name
    file_name = file_dialog.go()
    try:
        img = Image.open(file_name)
    except:
        print 'openfile error'
    show_img.image = img
    show_img.pack()
 
 
def gen():
    try:
        img_o = Image.open(file_name)
    except:
        print 'openfile error'
    img_L = img_o.convert('L')
    size_x, size_y = img_o.size
    size_y = size_y * 80 / size_x / 2
    size_x = 80
#img_L.resize((size_x, size_y)).show()
    data = list(img_L.resize((size_x, size_y)).getdata())
 
    min_x, min_y = size_x, size_y
    max_x, max_y = 0, 0
 
    for i in range(0, size_y):
        for j in range(0, size_x):
            index = i * size_x + j
            if data[index] <= 170:
                min_x, min_y = min(min_x, j), min(min_y, i)
                max_x, max_y = max(max_x, j), max(max_y, i)
    genText.delete('1.0', 'end')
    for i in range(min_y, max_y + 1):
        for j in range(min_x, max_x + 1):
            index = i * size_x + j
            if data[index] > 170:
                to = ' '
            elif data[index] > 85:
                to = '1'
            else:
                to = '0'
            genText.insert('end', to)
        #print
        genText.insert('end', '\n')
 
 
 
if __name__ == "__main__":
      
    mainWindow = Tk()
    mainWindow.title()
    #mainWindow.geometry('640x480+0+0')
     
    frame = Frame(mainWindow)
    frame.pack()
     
    fileBotton = Button(frame, text =u"打开文件", command = getFileName)
    fileBotton.pack(side = LEFT)
     
    genBotton = Button(frame, text = u"生成", command = gen)
    genBotton.pack(side = LEFT)
     
    genText = Text(frame, height = 40)
    genText.pack(fill = BOTH, padx = 10, pady = 10)
     
    show_img = Label(frame)
    show_img.pack()
    mainWindow.mainloop()

Posted by xhSong Filed in python Tagged by python bit map 萌 Comments[1]

一个弱爆的google 翻译客户端

2012年10月10日 02:06

在ubuntu下每次想翻译一个词或者一句话都要开浏览器上google翻译，感觉挺麻烦。于是自己写了一个python小脚本（googleTranslate.py），简化这个流程。

 

?
googleTranslate.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/python
# coding=utf-8
 
import urllib,urllib2
import sys
if __name__ == '__main__':
    if len(sys.argv) < 2:
        exit()
    tolanguage = 'en'
    text = ""
    if sys.argv[1] == 'en':
        tolanguage = 'en'
    elif sys.argv[1] == 'ch':
        tolanguage = 'zh-CN'
    else:
        text = sys.argv[1]
    for i in range(2, len(sys.argv)):
        text += sys.argv[i] + " "
    values = {'client':'t', 'text': text, 'hl':'en', 'sl':'auto', 'tl':tolanguage, 'ie':'UTF-8', 'oe':'UTF-8', 'multires':'1', 'otf':'2', 'ssel':'0', 'tsel':'0', 'sc':'1'}
    url = 'http://translate.google.cn/translate_a/t'
    request = urllib2.Request(url, urllib.urlencode(values))
    request.add_header('User-Agent', "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.4 (KHTML, like Gecko) Chrome/22.0.1229.79 Safari/537.4")
    response = urllib2.urlopen(request)
    data = response.read()
    #print data
    frags = data[4:data.find("]]")].split("\"],[\"")
    totext = ""
    for frag in frags:
        totext += frag.split("\",\"")[0]
    print totext

将这个脚本放在某个目录下，此处以/path/to为例子。使用以下命令添加脚本可执行属性

?
1
chmod +x googleTranslate.py

然后在.bashrc最后添加一行

?
1
alias t='/path/to/googleTranslate.py'

于是乎在任何界面下想要翻译词句子，直接ctrl+alt+t，输入

?
1
t 想要翻译的词句

即可。默认是将词句翻译成英文，如果需要将其他语言翻译成中文，执行

?
1
t ch 想要翻译的词句

即可。方便快捷，o(∩∩)o...哈哈

 

而后觉得写成一个小软件还是很靠谱的，于是又折腾了下python Tkinter，把上面的代码加了一个GUI的外壳。废话少说，上图

GUI的代码也不复杂，顺便也贴了吧，供大家交流。BUG比较多，有待后期改进，谢谢阅读！

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/python
# coding=utf-8
 
import urllib, urllib2
from Tkinter import *
from ttk import Combobox
  
def translate():
    tolanguage = languageMap[option.get()]
    text = startText.get('1.0', 'end').encode('utf-8')
     
    values = {'client':'t', 'text': text, 'hl':'en', 'sl':'auto', 'tl':tolanguage, 'ie':'UTF-8', 'oe':'UTF-8', 'multires':'1', 'otf':'2', 'ssel':'0', 'tsel':'0', 'sc':'1'}
    url = 'http://translate.google.cn/translate_a/t'
    request = urllib2.Request(url, urllib.urlencode(values))
    request.add_header('User-Agent', "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.4 (KHTML, like Gecko) Chrome/22.0.1229.79 Safari/537.4")
    response = urllib2.urlopen(request)
    data = response.read()
    print data
     
    frags = data[4:data.find("]]")].split("\"],[\"")
    totext = ""
    for frag in frags:
        totext += frag.split("\",\"")[0]
     
    toText.delete('1.0', 'end')
    toText.insert('1.0', totext.replace("\\n", "\n"))
 
if __name__ == "__main__":
     
    mainWindow = Tk()
    mainWindow.title(u"Google 翻译 by hustsxh@gmail.com")
    #mainWindow.geometry('640x480+0+0')
     
    frame = Frame(mainWindow)
    frame.pack()
     
    Label(frame, text = u'翻译成：').pack(side = LEFT)
     
    languageMap = {'English': 'en', u'中文简体': 'zh-CN', u'中文繁體': 'zh-TW', u'日本語': 'ja', u'한국의': 'ko', u'Deutsch': 'de', u'русский': 'ru', u'française': 'fr'}
    defaultLanguage = StringVar(frame, 'English')
    option = Combobox(frame, text = defaultLanguage, values = languageMap.keys())
    option.pack(side = LEFT)
     
    transBotton = Button(frame, text =u"翻译", command = translate)
    transBotton.pack(side = LEFT)
     
    startText = Text(mainWindow, height = 15)
    startText.pack(fill = BOTH, padx = 10, pady = 10)
     
    toText = Text(mainWindow, height = 15)
    toText.pack(fill = BOTH, padx = 10, pady = 10)
     
    mainWindow.mainloop()

Posted by xhSong Filed in python Tagged by python 翻译 google translate Comments[3]