website/code/Genetic_algorithm.html at master · nodebox/website

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

<html>

<head>

<title>NodeBox | Genetic algorithm</title>

</head>

<ol>

<li><a class="node" href="/code/Home">NodeBox 1</a>

<li><a href="/">Homepage</a></li>

<li><a href="/node/">NodeBox 3Node-based app for generative design and data visualization</a></li>

<li><a href="/opengl/">NodeBox OpenGLHardware-accelerated cross-platform graphics library</a></li>

<li><a href="/code/Home">NodeBox 1Generate 2D visuals using Python code (Mac OS X only)</a></li>

</ol>

</li>

<li><a class="gallery" href="/gallery/">Gallery</a></li>

<li><a class="documentation" href="/code/Tutorial">Documentation</a></li>

<li><a class="forum" href="http://support.nodebox.net/discussions">Forum</a></li>

</ol>

</div>

<a href="/code/Home"><h1>NodeBox</h1>

Create visual output with Python programming code

</a></div>

</div>

</form>

</div>

<a href="/code/Download">Download</a>

<a href="/code/Reference">Reference</a>

<a href="/code/Tutorial">Tutorial</a>

<a href="/code/Library">Library</a>

<a href="/code/Gallery">Gallery</a>

<a href="/code/About">About</a>

</div>

</div>

<h3>Genetic algorithm</h3>

A genetic algorithm is a <a href="http://en.wikipedia.org/wiki/Stochastic" target="_self">stochastic</a> search method based on natural selection and reproduction of a population of individuals. Each generation, the fittest candidates in the population are selected, paired, and recombined into a new generation. With each new generation the system converges towards an optimal fitness. Optimal fitness can be global or local:<ul><li>The global optimum is the optimal solution among all possible solutions; the GA's goal.</li><li>The local optimum occurs when the GA converges too fast and gets trapped. </li></ul>Local optima occur when the population is no longer diverse enough. Therefore, we need to preserve some weaker candidates whose role can become more prominent later on. A detailed paper on optima and hierarchical fair competition (Jianjun Hu et al.) is <a href="ftp://ftp.cs.bham.ac.uk/pub/authors/W.B.Langdon/biblio/gecco2002/GP195.pdf" target="_blank">here</a>. <hr size="2" width="100%" /><h2>Grid symmetry example </h2>Let's have a look at an example. During the<a href="http://workshops.nodebox.net/2009" target="_blank"> 2009 NodeBox workhop</a> in Finland (Lahti University of Applied Sciences, Institute of Design) Jonatan Hilden and I composed a simple genetic algorithm for NodeBox that we wanted to share with you.To make it work, you have to code three things yourself: <ul><li>Candidate: the members in a population that are going to improve through evolution</li><li>Recombination function: what candidate comes out of the crossing of two parent candidates?</li><li>Fitness function:  calculates the "score" of a candidate. </li></ul>We've included a grid candidate with black and white squares that will strive for symmetry. In the image below you can see how generations of grids evolve over time: <img src="/code/data/media/genetic_algorithm.jpg" alt="genetic_algorithm" />  If you look at the source code of the grid candidate closely you'll see that it is just a list of True or False switches (True means black square in the grid, False means white square in the grid). The candidate furthermore has some helper methods to find out what squares surround the current one. These are used in the fitness function to discover symmetrical patterns. Grids that have more symmetry (whose black squares have a horizontal and/or vertical reflection) score better, and will therefore be able to reproduce parts of their DNA (the list of True/False values) more often. <hr size="2" width="100%" /><h2>Source code</h2>Naturally, a candidate can be many other things beside a grid of black and white squares (a creature, source code, ...) A fairly easy first experiment would be to adapt the grid's DNA list to work with many colors instead of just black and white.<pre class="python"># A genetic algorithm is a stochastic search method based on

# natural selection and reproduction of a population of individuals.

# Each generation, the fittest candidates in the population are selected,

# paired, and recombined into a new generation.

# With each new generation the system converges towards an optimal fitness.

# Optimal fitness can be global or local.

# - The global optimum is the optimal solution among all possible solutions;

# the goal of the the GA.

# - The local optimum occurs when the GA converges too fast and is trapped.

# This occurs when the population is no longer diverse enough.

# Therefore, we need to preserve some weaker candidates whose role

# can become more prominent later on.

# - Stochastic: the process of selecting the fittest candidates in

# the population involves an amount of randomness, so weaker candidates

# are sometimes preserved.

# - Convergence: the approach toward a definite value or equilibrium state.

# We can use some extra computing power:

try:

import psyco

psyco.full()

except:

pass

### GENETIC ALGORITHM FUNCTIONS ##########################################

def candidate():

# Needs to be implemented.

return None

def recombine(a, b, crossover=0.5):

# Needs to be implemented.

return None

def fitness(candidate):

# Needs to be implemented.

return 0

def population(size=500):

""" Returns an initial list of random candidates (e.g. generation 0).

"""

return [candidate() for i in range(size)]

def sort_by_fitness(candidates):

""" Returns a sorted list of (fitness, candidate)-tuples; best-first.

"""

return sorted([(fitness(x), x) for x in candidates], reverse=True)

def select(population, top=0.7, determinism=0.8):

""" Returns a selection of fit candidates from the population.

- top: roughly the fittest 70% candidates are allowed to reproduce.

- determinism: there is a 20% chance that good candidates are ignored,

this keeps the population diverse.

"""

population = sort_by_fitness(population)

population = [candidate for (fitness, candidate) in population]

parents = list(population)

i = len(parents)

while len(parents) > len(population)*top:

i = (i-1) % len(parents)

if random() < determinism:

parents.pop(i)

return parents

def reproduce(population, top=0.7, determinism=0.8, crossover=lambda: random()):

""" Returns a new population of candidates.

Selects parent that are fit to reproduce.

Recombines random pairs of parents to new child candidates.

"""

parents = select(population, top, determinism)

children = []

for i in range(len(population)):

i = random(len(parents))

j = choice( range(0,i) + range(i+1, len(parents)) )

k = crossover

try: k = k()

except:

pass

children.append(recombine(parents[i], parents[j], crossover=k))

return children

def converged(population):

""" Returns True when the population has reached its optimum.

"""

for i in range(1, len(population)):

if population[i-1] != population[i]:

return False

return True

### GRID CANDIDATE #######################################################

# Any kind of candidate can be used in the GA.

# Here's an example of random black & white grids that score better

# as they become more symmetrical.

# We just create one candidate (or agent) with a fitness property and

# the capability to recombine; the GA functions will create a population

# and keep improving it until it converges.

# Internally, the grid is just a list of colors (in this case: True (black)

# or False (white)). This makes it an ideal candidate to work with:

# lists are easy to examine and cut-and-splice in the recombine function.

# You can imagine how the values in the list could encompass a wider range

# of colors(for example: 0=black, 1=white, 2=red, ...)

class GridCandidate(list):

def __init__(self, rows, cols, values=[]):

self.rows = rows

self.cols = cols

# Cells in the grid are randomly black (True) or white (False).

if len(values) == 0:

values = [choice((True, False)) for i in range(rows*cols)]

list.__init__(self, values)

def draw(self, x, y, scale=10.0):

for i in range(self.cols):

for j in range(self.rows):

is_black = self[i+j*cols]

_ctx.fill(int(not is_black))

_ctx.oval(x+i*scale, y+j*scale, scale, scale)

# Triangles:

#R = 1.11803398875 # equilateral width/height ratio

#_ctx.push()

#_ctx.translate(x+i*scale/2, y+j*scale/R)

#if i % 2 == int(j & 2 == 0): # up for odd col in even row

# _ctx.beginpath(0, 0)

# _ctx.lineto(scale/2, scale/R)

# _ctx.lineto(scale, 0)

#else:

# _ctx.beginpath(0, scale/R)

# _ctx.lineto(scale/2, 0)

# _ctx.lineto(scale, scale/R)

#_ctx.endpath()

#_ctx.pop()

def contains(self, i):

return i > 0 and i < len(self)

def row(self, i): return i / self.cols # the row index i is in

def col(self, i): return i % self.cols # the column index i is in

def reflect(self, i, axis="horizontal"):

""" Returns the index in the grid that is symmetrical to this one.

For example:

0 1 2 3 4

5 6 7 8 9

reflect(1, "horizontal") => 3

reflect(4, "vertical") => 9

"""

if axis == "horizontal":

return self.row(i)*self.cols + self.cols - self.col(i) - 1

if axis == "vertical":

return (self.rows-self.row(i)-1)*self.cols + self.col(i)

def recombine(self, other, crossover=0.5):

i = int(len(self) * crossover)

return GridCandidate(self.rows, self.cols, values=self[:i]+other[i:])

@property

def fitness(self):

# Fitness is calculated in terms of symmetry.

# Grids with the same color at symmetrical positions score better.

score = 0

for i in range(len(self)):

j = self.reflect(i, "horizontal")

if self.contains(j) and self[j] == self[i]:

score += 1

j = self.reflect(i, "vertical")

score += 1

return score

# Here are some functions you may want to use to determine fitness:

def above(self, i) : return i-self.cols

def below(self, i) : return i+self.cols

def left( self, i) : return i+1

def right(self, i) : return i-1

north, south, east, west = above, below, left, right

def northeast(self, i) : return self.north(self.east(i))

def northwest(self, i) : return self.north(self.west(i))

def southeast(self, i) : return self.south(self.east(i))

def southwest(self, i) : return self.south(self.west(i))

# Grid size.

rows = 5

cols = 5

candidate = lambda: GridCandidate(rows, cols)

recombine = lambda a, b, crossover: a.recombine(b, crossover)

fitness = lambda candidate: candidate.fitness

# The initial random population:

p = population(size=500)

size(800, 2000)

# Process n generations:

for i in range(40):

p = reproduce(p, top=0.6, determinism=0.65)

#translate(0, 35)

#push()

#for candidate in p[:15]:

# translate(35, 0)

# candidate.draw(0, 0, scale=5)

#pop()

if converged(p):

print "converged at generation ", str(i)

break

# A list of scores for each member in the final population:

#print [score for score, x in sort_by_fitness(p)]

# The best solution in the final population:

p[0].draw(20, 20, scale=30)</pre></pre>      Created by Jonatan Hilden and Tom De Smedt Jonatan will be doing his thesis at the Experimental Media Group and is working on a library for recombinable vector artwork.

</div>

</div>

</div>

try{e=document.getElementsByTagName("span");for(i=0;i<e.length;i++){if(e[i].className=="header_image"){src=e[i].getElementsByTagName("img")[0].src;document.getElementById("header_image").src=src;break;}}}catch(e){}

</script>

</body>

</html>

FilesExpand file tree

Genetic_algorithm.html

Latest commit

History

Genetic_algorithm.html

File metadata and controls