-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathopevo.py
141 lines (131 loc) · 5.36 KB
/
opevo.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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
import sys
import random
import time
import oph
#fitness will take a set s and a set of weights and return a tuple containing the fitness and the best path
def fitness( chrom, s, start_point, end_point, tmax ):
augs = []
for i in xrange( len( s ) ):
augs.append( ( s[ i ][0],
s[ i ][1],
s[ i ][2],
s[ i ][3],
s[ i ][4] + chrom[ i ] ) )
if debug:
print 'fitness---------------------------------'
print 'augs:'
print augs
#best = oph.ellinit_replacement( augs, start_point, end_point, tmax )
ellset = oph.ell_sub( tmax, start_point, end_point, augs )
#best = oph.initialize( ellset, start_point, end_point, tmax )[0]
best = oph.init_replacement( ellset, start_point, end_point, tmax )[0]
if debug:
print 'best:'
print best
print 'best real reward:'
print [ x[3] for x in best ]
print len( s )
print [ s[ x[3] - 2 ] for x in best[ 1:len( best ) - 1 ] ]
print [ s[ x[3] - 2 ][2] for x in best[ 1:len( best ) - 1 ] ]
print ( sum( [ s[ x[3] - 2 ][2] for x in best[ 1:len( best ) - 1 ] ] ), best )
return ( sum( [ s[ x[3] - 2 ][2] for x in best[ 1:len( best ) - 1 ] ] ), best )
def crossover( c1, c2 ):
assert( len( c1 ) == len( c2 ) )
point = random.randrange( len( c1 ) )
first = random.randrange( 2 )
if( first ):
return c1[:point] + c2[point:]
else:
return c2[:point] + c1[point:]
def mutate( chrom, mchance, msigma ):
return [ x + random.gauss( 0, msigma ) if random.randrange( mchance ) == 0 else
x for x in chrom ]
def run_alg( f, tmax, N ):
random.seed()
cpoints = []
an_unused_value = f.readline() # ignore first line of file
for i in xrange( N ):
cpoints.append( tuple( [ float( x ) for x in f.readline().split() ] + [ i, 0 ] ) )
start_point = cpoints.pop( 0 )
end_point = cpoints.pop( 0 )
assert( oph.distance( start_point, end_point ) < tmax )
popsize = 10
genlimit = 10
kt = 5
isigma = 10
msigma = 7
mchance = 2
elitismn = 2
if( debug ):
print 'data set size:', len( cpoints ) + 2
print 'tmax: ', tmax
print 'N: ', N
print 'parameters:'
print 'generations: ', genlimit
print 'population size: ', popsize
print 'ktournament size:', kt
print 'mutation chance: ', mchance
print str( elitismn ) + '-elitism'
start_time = time.clock()
#generate initial random population
pop = []
for i in xrange( popsize + elitismn ):
chrom = []
for j in xrange( len( cpoints ) ):
chrom.append( random.gauss( 0, isigma ) )
chrom = ( fitness( chrom, cpoints, start_point, end_point, tmax )[0], chrom )
while( i - j > 0 and j < elitismn and chrom > pop[ i - 1 - j ] ):
j += 1
pop.insert( i - j, chrom )
bestfit = 0
for i in xrange( genlimit ):
nextgen = []
for j in xrange( popsize ):
#select parents in k tournaments
parents = sorted( random.sample( pop, kt ) )[ kt - 2: ] #optimize later
#crossover and mutate
offspring = mutate( crossover( parents[0][1], parents[1][1] ), mchance, msigma )
offspring = ( fitness( offspring, cpoints, start_point, end_point, tmax )[0], offspring )
if( offspring[0] > bestfit ):
bestfit = offspring[0]
print bestfit
if( elitismn > 0 and offspring > pop[ popsize ] ):
l = 0
while( l < elitismn and offspring > pop[ popsize + l ] ):
l += 1
pop.insert( popsize + l, offspring )
nextgen.append( pop.pop( popsize ) )
else:
nextgen.append( offspring )
pop = nextgen + pop[ popsize: ]
bestchrom = sorted( pop )[ popsize + elitismn - 1 ]
end_time = time.clock()
print 'time:'
print end_time - start_time
print 'best fitness:'
print bestchrom[0]
print 'best path:'
best_path = fitness( bestchrom[1], cpoints, start_point, end_point, tmax )[1]
print [ x[3] for x in best_path ]
print 'their stuff:'
stuff = oph.initialize( oph.ell_sub( tmax, start_point, end_point, cpoints )
, start_point, end_point, tmax )[0]
print 'fitness:', sum( [ x[2] for x in stuff ] )
print 'my stuff:'
stuff2 = oph.ellinit_replacement( cpoints, start_point, end_point, tmax )
print 'fitness:', sum( [ x[2] for x in stuff2 ] )
print 'checking correctness...',
total_distance = ( oph.distance( start_point, cpoints[ best_path[ 1 ][3] - 2 ] ) +
oph.distance( end_point, cpoints[ best_path[ len( best_path ) - 2 ][3] - 2 ] ) )
for i in xrange( 1, len( best_path ) - 3 ):
total_distance += oph.distance( cpoints[ best_path[ i ][3] - 2 ],
cpoints[ best_path[ i + 1 ][3] - 2 ] )
print 'OK' if total_distance <= tmax else 'not OK'
print 'tmax: ', tmax
print 'total distance:', total_distance
return ( bestchrom[0], end_time - start_time )
if( __name__ == '__main__' ):
debug = True if 'd' in sys.argv else False
run_alg( open( sys.argv[1] ), int( sys.argv[2] ), int( sys.argv[3] ) )
else:
debug = False