evolve.py 7.2KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300
  1. # -*- coding: utf-8 -*-
  2. ################################################################################
  3. import sys
  4. from random import randint
  5. ################################################################################
  6. DEFAULT_MUT_RATE = 0.1
  7. DEFAULT_POP_MAX = 100
  8. DEFAULT_TRY_MAX = 1000
  9. ################################################################################
  10. INITDATA_FUNC = None
  11. FITNESS_FUNC = None
  12. RECOMBINE_FUNC = None
  13. MUTATE_FUNC = None
  14. EVOLVE_FUNC = None
  15. HASSOLUTION_FUNC = None
  16. ################################################################################
  17. # mutation global helper variables
  18. toMutatePerPop = 0
  19. mutatedPerPop = 0
  20. mutCnt = 0
  21. tryCnt = 0
  22. ################################################################################
  23. mutationRate = DEFAULT_MUT_RATE # %
  24. popMax = DEFAULT_POP_MAX
  25. tryMax = DEFAULT_TRY_MAX
  26. storeHistory = False
  27. ################################################################################
  28. bestDNA = None
  29. dna_history = []
  30. ################################################################################
  31. def chooseRandomChromosome(dna):
  32. n = randint(0, len(dna) - 1)
  33. return n
  34. ################################################################################
  35. def hasSolution(dnaList):
  36. global FITNESS_FUNC
  37. found = False
  38. for dna in dnaList:
  39. if FITNESS_FUNC(dna) == True:
  40. found = True
  41. break
  42. return { 'found' : found, 'dnaList' : dnaList }
  43. ################################################################################
  44. def evolve(dnaList, mx):
  45. if len(dnaList) % 2 != 0 \
  46. or len(dnaList) == 0 \
  47. or mx % 2 != 0:
  48. return []
  49. cnt = 0
  50. tmpdnaList = []
  51. for i in range(0, len(dnaList), 2):
  52. # get two dna objects and recombine them
  53. a = dnaList[i]
  54. b = dnaList[i + 1] # darum muss popMax % 2 == 0 sein, sonst gibt es hier ein Problem
  55. tmpList = RECOMBINE_FUNC(a, b)
  56. for d_new in tmpList:
  57. # add the new combined dna - after mutation - to the dna list
  58. MUTATE_FUNC(d_new)
  59. tmpdnaList.append(d_new)
  60. cnt = cnt + 1
  61. if cnt == mx:
  62. break # already max new DNA objects generated
  63. if cnt == mx:
  64. break # already popMax new DNA objects generated
  65. return tmpdnaList
  66. ################################################################################
  67. # a simple single core implementation to use the genetic algorithm way to solve a problem
  68. def autorun():
  69. global tryCnt
  70. global tryMax
  71. global popMax
  72. global mutatedPerPop
  73. global storeHistory
  74. global dna_history
  75. global bestDNA
  76. ##########
  77. dnaList = INITDATA_FUNC(popMax)
  78. bestDNA = None
  79. ##########
  80. tryCnt = 0
  81. found = False
  82. while tryCnt < tryMax and found == False:
  83. # calculate the fitness for the last popMax elements
  84. # evaluate
  85. tmp = HASSOLUTION_FUNC(dnaList)
  86. found = tmp['found']
  87. dnaList = tmp['dnaList']
  88. #print dnaList
  89. if storeHistory == True:
  90. dna_history = dna_history + dnaList
  91. if found == False:
  92. # generate a list of dna objects sorted by the previous evaluated fitness descending
  93. # selection
  94. #print dnaList
  95. latestGeneration = list(reversed(sorted(dnaList, key=lambda k: k['fit'])))
  96. #print "LB=" + str(len(latestGeneration))
  97. if bestDNA == None or (bestDNA != None and latestGeneration[0]['fit'] > bestDNA['fit']):
  98. bestDNA = latestGeneration[0] # remember the DNA with the best fitness level
  99. dnaList = EVOLVE_FUNC(latestGeneration, popMax)
  100. #print "LA=" + str(len(dnaList))
  101. mutatedPerPop = 0 # reset the counter of the mutations per population for the next evolution/mutation progress
  102. else:
  103. break # abort the while loop
  104. tryCnt = tryCnt + 1
  105. if found == False:
  106. # evaluate the last recombined and mutated population if there was no solution found before
  107. tmp = HASSOLUTION_FUNC(dnaList)
  108. dnaList = tmp['dnaList']
  109. if storeHistory == True:
  110. dna_history = dna_history + dnaList
  111. latestGeneration = list(reversed(sorted(dnaList, key=lambda k: k['fit'])))
  112. if bestDNA != None and latestGeneration[0]['fit'] > bestDNA['fit']:
  113. bestDNA = latestGeneration[0]
  114. return bestDNA
  115. ############################################################################
  116. def resetToDefaults():
  117. global DEFAULT_MUT_RATE
  118. global DEFAULT_POP_MAX
  119. global DEFAULT_TRY_MAX
  120. global mutationRate
  121. global popMax
  122. global tryMax
  123. global tryCnt
  124. global storeHistory
  125. mutationRate = DEFAULT_MUT_RATE
  126. popMax = DEFAULT_POP_MAX
  127. tryMax = DEFAULT_TRY_MAX
  128. tryCnt = 0
  129. storeHistory = False
  130. ############################################################################
  131. def init(f, m, r, i, pm = DEFAULT_POP_MAX, mr = DEFAULT_MUT_RATE, tm = DEFAULT_TRY_MAX, e = evolve, h = hasSolution):
  132. global toMutatePerPop
  133. global mutationRate
  134. global popMax
  135. global tryMax
  136. global tryCnt
  137. global INITDATA_FUNC
  138. global FITNESS_FUNC
  139. global RECOMBINE_FUNC
  140. global EVOLVE_FUNC
  141. global MUTATE_FUNC
  142. global HASSOLUTION_FUNC
  143. global dna_history
  144. tryCnt = 0
  145. tryMax = tm
  146. popMax = pm
  147. mutationRate = mr
  148. recalcToMutatePerPop()
  149. INITDATA_FUNC = i
  150. FITNESS_FUNC = f
  151. RECOMBINE_FUNC = r
  152. MUTATE_FUNC = m
  153. EVOLVE_FUNC = e
  154. HASSOLUTION_FUNC = h
  155. dna_history = []
  156. ############################################################################
  157. def recalcToMutatePerPop():
  158. global toMutatePerPop
  159. global mutatedPerPop
  160. global mutationRate
  161. mutatedPerPop = 0
  162. toMutatePerPop = (popMax * mutationRate) / 100.0
  163. ############################################################################
  164. def shouldBeMutated():
  165. global mutatedPerPop
  166. global toMutatePerPop
  167. global mutCnt
  168. #if (randint(0, 1) == 1 and mutatedPerPop < toMutatePerPop):
  169. #print "m:" + str(mutatedPerPop < toMutatePerPop)
  170. if randint(0, 1) == 1 and mutatedPerPop < toMutatePerPop:
  171. mutCnt = mutCnt + 1
  172. mutatedPerPop = mutatedPerPop + 1
  173. return True
  174. return False
  175. ############################################################################
  176. # setter functions
  177. def setStoreHistory(b):
  178. global storeHistory
  179. storeHistory = b
  180. def setDNAHistory(hl):
  181. global dna_history
  182. dna_history = hl
  183. def setMutCnt(mc):
  184. global mutCnt
  185. mutCnt = mc
  186. def setPopMax(pm):
  187. global popMax
  188. popMax = pm
  189. ############################################################################
  190. # getter functions
  191. def getPopMax():
  192. global popMax
  193. return popMax
  194. def getMutRate():
  195. global mutationRate
  196. return mutationRate
  197. def getMutCnt():
  198. global mutCnt
  199. return mutCnt
  200. def getTryMax():
  201. global tryMax
  202. return tryMax
  203. def getTryCnt():
  204. global tryCnt
  205. return tryCnt
  206. def getStoreHistory():
  207. global storeHistory
  208. return storeHistory
  209. def getStoredHistory():
  210. global dna_history
  211. return dna_history
  212. def getProgress():
  213. global tryCnt
  214. global tryMax
  215. return (100.0 * tryCnt / tryMax)
  216. def getBestDNA():
  217. global bestDNA
  218. return bestDNA
  219. ############################################################################
  220. # getter for immutables
  221. def getDefaultPopMax():
  222. global DEFAULT_POP_MAX
  223. return DEFAULT_POP_MAX
  224. def getDefaultMutRate():
  225. global DEFAULT_MUT_RATE
  226. return DEFAULT_MUT_RATE
  227. def getDefaultTryMax():
  228. global DEFAULT_TRY_MAX
  229. return DEFAULT_TRY_MAX
  230. # end