用遗传算法求复杂函数的极值点
之前也接触过遗传算法，只是没有实践，正巧这次模式识别的课程上老师提到，并布置了一个小练习题，便拿来做做吧。
题目本来要求是求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语言表示为
k = randint(1, 23) mask = (1<<k) - 1 C = A & mask | B & ~mask D = B & mask | A & ~mask
变异方式：随机选取24个二进制位中的某一个，如果该位0变成则变成1，否则变成0
确定遗传
在元素个体，遗传得到的个体和变异个体中选取最好的30个个体(对应的函数值最大的30个个体)作为下一次迭代的父样本。
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)
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次迭代，结果基本稳定。
2016年12月17日 21:59
如何用binary search 计算 y = -(x-0.4)**2+10 maximum point?
2023年4月21日 20:38
TeachersBadi is information about education, students and teachers.‘TeachersBadi‘, the name itself discloses the nature of the site. The site is being launched and run by a dedicated Team for teachers, students and educators. We love to share mainly educational information teachersbadi.in and employees, teacher’s related content in the education world.TeachersBadi is information about education, students and teachers.‘TeachersBadi‘, the name itself discloses the nature of the site. The site is being launched and run by a dedicated Team for teachers, students and educators.
2023年11月01日 18:06
This specific is generally clearly basic and in addition exceptional truth alongside without a doubt reasonable and besides in fact valuable My business is seeking find ahead of time intended for this particular helpful stuff
2024年1月16日 21:11
이봐, 내가 만난 멋진 게시물이 지난 일주일 동안 비슷한 종류의 게시물을 찾고 있었지만 거의 발견하지 못했습니다. 대단히 감사 드리며 더 많은 게시물을 찾을 것입니다.
2024年1月23日 20:04
귀하의 블로그가 너무 놀랍습니다. 나는 내가보고있는 것을 쉽게 발견했다. 또한 콘텐츠 품질이 굉장합니다. 넛지 주셔서 감사합니다!
2024年2月19日 17:19
나는 당신이 이것에 배치 한 각각의 공연을 즐깁니다. 정말 유용한 곳이 될 거라고 확신합니다. 나는 또한 기뻤다. 잘 했어!
2024年2月21日 23:20
꽤 좋은 게시물입니다. 방금 귀하의 블로그를 우연히 발견하고 귀하의 블로그 게시물을 읽는 것이 정말 즐거웠다고 말하고 싶었습니다. 어떤 식 으로든 피드를 구독하고 곧 다시 게시 해 주시기 바랍니다. 유용한 정보에 감사드립니다.
2024年2月24日 15:02
팁들 주셔서 감사합니다. 그들은 모두 훌륭했습니다. 나는 정신적으로나 육체적으로 뚱뚱해지는 데 문제가 있습니다. 여러분 덕분에 개선을 보여주고 있습니다. 더 게시하십시오.
2024年2月24日 15:03
팁들 주셔서 감사합니다. 그들은 모두 훌륭했습니다. 나는 정신적으로나 육체적으로 뚱뚱해지는 데 문제가 있습니다. 여러분 덕분에 개선을 보여주고 있습니다. 더 게시하십시오.
2024年2月24日 15:47
This is really likewise an incredibly beneficial placing most of us severely encountered shopping as a result of. It truly is faraway from each and every day we have now possibility to think about something
2024年2月24日 17:05
이러한 유형의 주제를 검색하는 거의 모든 사람들에게 도움이되기를 바랍니다. 저는이 웹 사이트가 그러한 주제에 가장 적합하다고 생각합니다. 좋은 작품과 기사의 품질.
2024年2月24日 17:24
귀하의 블로그가 너무 놀랍습니다. 나는 내가보고있는 것을 쉽게 발견했다. 또한 콘텐츠 품질이 굉장합니다. 넛지 주셔서 감사합니다!
2024年2月24日 18:01
귀하의 블로그가 너무 놀랍습니다. 나는 내가보고있는 것을 쉽게 발견했다. 또한 콘텐츠 품질이 굉장합니다. 넛지 주셔서 감사합니다!
2024年2月24日 19:23
귀하의 블로그가 너무 놀랍습니다. 나는 내가보고있는 것을 쉽게 발견했다. 또한 콘텐츠 품질이 굉장합니다. 넛지 주셔서 감사합니다!
2024年2月24日 20:48
꽤 좋은 게시물입니다. 나는 방금 귀하의 블로그를 우연히 발견하고 귀하의 블로그 게시물을 읽는 것이 정말 즐거웠다고 말하고 싶었습니다. 어떤 식 으로든 피드를 구독하고 곧 다시 게시 해 주시기 바랍니다. 유용한 정보에 감사드립니다.
2024年2月24日 22:35
귀하의 블로그가 너무 놀랍습니다. 나는 내가보고있는 것을 쉽게 발견했다. 또한 콘텐츠 품질이 굉장합니다. 넛지 주셔서 감사합니다!
2024年2月25日 14:46
전 세계적으로 매우 어려운시기가 될 것이기 때문에 저는이 정보를 절대적으로 좋아합니다. 좋은 일이 확실히오고있다
2024年2月25日 15:13
블로그에 대한 흥미로운 주제. 나는 재미를 위해 인터넷을 검색하고 당신의 웹 사이트를 찾았습니다. 멋진 포스트. 지식을 공유해 주셔서 감사합니다! 일부 사람들이 여전히 웹 사이트를 관리하는 데 노력을 기울이는 것을 보는 것이 좋습니다. 곧 다시 확인하겠습니다.
2024年2月25日 15:47
"초기 당신은 멋진 블로그를 얻었습니다. 나는 결심에 더하기 균일 한 분을 포함합니다. 나는 당신이 정말로 매우 기능적인 문제를 가지고 있다고 생각합니다. 나는 항상 당신의 블로그 축복을 확인하고 있습니다.
2024年2月25日 18:43
Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that "The content of your post is awesome" Great work