Changeset 1980 in genesis for nodes/prepconf.py
- Timestamp:
- Apr 11, 2004, 2:01:11 AM (21 years ago)
- File:
-
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
nodes/prepconf.py
r1937 r1980 1 # experiment met evolutionary programming voor de kanalenplanning 2 # het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld 3 # fout. wat er wel goed in zit is het parseren van de bestaande situatie en 4 # het scoren van (nu random) configuraties. 5 # 6 # de score functie is nu redelijk simplistisch: 7 # - de score van een combinatie van twee interfaces op een node is 1 als er 8 # twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5 9 # als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn 10 # - de score van een node is de som van de scores van alle combinaties van 11 # interfaces van die node, maal het aantal interfaces. dat laatste omdat 12 # een positieve score hebben knapper is met meer interfaces dan met minder, 13 # dus dat moet beloond. een negatieve score is erger met meer interfaces 14 # (belangrijker node, waarschijnlijk) dan met minder, dus dat moet 15 # bestraft. 16 # - de totale score is de som van de scores van de nodes 17 # 18 # het stukje "genetisch" aan het einde is afgeraffeld. mutation en 19 # recombination gebeuren op de oplossing zelf ipv op een bitstring 20 # representatie. selection is dom en neemt gewoon de helft beste oplossingen. 21 # 22 # lvoge@cs.vu.nl 1 # gegeven een file met een lijst van te gebruiken wleiden.conf's, print 2 # op stdout een file waar channelga.ml wat mee kan. 23 3 import re 24 import random25 import os26 27 # deze twee zijn nodig voor de evaluatie van een configuratie28 nodes = {} # nodename -> Node29 groups = {} # essid -> WIGroup30 31 population = []32 33 # gegeven een lijst, geef de lijst zonder dubbele elementen34 def uniq(l):35 d = {}36 for e in l:37 d[e] = 138 return d.keys()39 40 class Node:41 def __init__(self, name, wis):42 self.name = name43 self.wis = wis44 self.special = {}45 for wi in wis:46 wi.setNode(self)47 def score(self):48 score = 049 for i in range(len(self.wis)):50 wi_i = self.wis[i]51 if wi_i.group == None:52 # orphaned interface53 continue54 if wi_i.group.channel == None:55 print "huh?"56 for j in range(len(self.wis)):57 if i != j:58 wi_j = self.wis[j]59 if wi_j.group == None:60 continue61 diff = abs(wi_i.group.channel - wi_j.group.channel)62 if diff > 2:63 score = score + 164 elif diff == 2:65 score = score - 166 elif diff == 1:67 score = score - 568 else:69 score = score - 1070 if self.special.has_key(wi_i.group.channel):71 score = score + self.special[wi_i.group.channel]72 score = score * len(self.wis)73 return score74 def setSpecialScoreForChannels(self, score, channels):75 for c in channels:76 self.special[c] = score77 78 # een supernode is een verzameling subnodes, bv cetim1, cetim2 en cetim3.79 class SuperNode(Node):80 def __init__(self, name, nodes):81 self.name = name82 self.nodes = nodes83 self.wis = []84 self.special = {}85 for n in nodes:86 self.wis.extend(n.wis)87 88 class WI:89 def __init__(self, name):90 self.name = name91 self.node = None92 self.group = None93 self.omni = 094 def setNode(self, node):95 self.node = node96 def setGroup(self, group):97 self.group = group98 99 class WIGroup:100 def __init__(self, name):101 self.name = name102 self.wis = []103 self.channel = None104 def add_wi(self, wi):105 self.wis.append(wi)106 wi.setGroup(self)107 def uniq(self):108 self.wis = uniq(self.wis)109 110 # een configuratie is een bepaalde bedeling van kanalen aan groepen. aangezien111 # groepen keyed zijn op essid is de concrete configuratie hier een dict van112 # essids naar kanalen.113 class Configuration:114 def __init__(self):115 self.conf = None116 self.calculated_score = None117 def copy(self):118 c = Configuration()119 c.conf = self.conf.copy()120 c.calculated_score = None121 return c122 def randomize(self):123 self.conf = {}124 for essid in groups.keys():125 self.conf[essid] = random.randint(1, 13)126 self.calculated_score = None127 def score(self):128 assert len(self.conf) == len(groups)129 if self.calculated_score != None:130 return self.calculated_score131 for essid in groups.keys():132 groups[essid].channel = self.conf[essid]133 score = 0134 for node in nodes.values():135 score = score + node.score()136 self.calculated_score = score137 return score138 def mutate(self, rate):139 for essid in groups.keys():140 if random.random() <= rate:141 self.conf[essid] = random.randint(1, 13)142 def crossover(self, partner, numpoints):143 # pick the crossover points144 essids = groups.keys()145 points = [random.randint(0, len(essids) - 1) for i in range(numpoints)]146 points.sort()147 conf = {}148 who = 0149 lastpoint = 0150 while len(points):151 point = points.pop(0)152 if who == 0:153 d = self.conf154 else:155 d = partner.conf156 who = 1 - who157 for i in range(lastpoint, point + 1):158 conf[essids[i]] = d[essids[i]]159 lastpoint = point160 if who == 0:161 d = self.conf162 else:163 d = partner.conf164 for i in range(lastpoint, len(essids)):165 conf[essids[i]] = d[essids[i]]166 assert len(conf) == len(groups)167 self.conf = conf168 169 170 # BEGIN UGLY PARSING CODE171 172 to_resolve = [] # list of (essid, WI) tuples173 4 174 5 def parse_wleiden_conf(lines): 175 6 essid = None 176 7 wi = None 177 wis = []178 8 for l in lines: 179 9 if wi != None: 180 match = re.match("^MODE=master.*", l)181 if match != None:182 master = 1183 10 match = re.match("^ESSID=(.*)", l) 184 11 if match != None: 185 essid = match.group(1)12 print match.group(1), 186 13 match = re.match("^EW[0-9]*", l) 187 14 if match != None: 188 if master == 1: 189 group = WIGroup(essid) 190 groups[essid] = group 191 group.add_wi(wi) 192 else: 193 # defer, may come way later 194 to_resolve.append( (essid, wi) ) 195 master = 0 15 wi = None 16 essid = None 17 match = re.match("^EOS", l) 18 if match != None: 196 19 wi = None 197 20 essid = None … … 199 22 match = re.match("^\$nodename='([^']*)';.*", l) 200 23 if match != None: 201 nodename = match.group(1).lower() 24 print "" 25 print match.group(1).lower(), 202 26 match = re.match("^\$config{'wi[0-9]*:[0-9].*", l) 203 27 if match != None: … … 205 29 match = re.match("^\$config{'(wi[0-9]*).*", l) 206 30 if match != None: 207 wi = WI(match.group(1)) 208 wis.append(wi) 209 master = 0 210 node = Node(nodename, wis) 211 nodes[nodename] = node 31 print match.group(1).lower(), 32 wi = 1 212 33 213 # gegeven een file met filenames van wleiden.conf's, parseer ze allemaal en 214 # vul de datastructuren 215 def parse_metafile(filename): 216 for fname in open(filename).readlines(): 217 parse_wleiden_conf(open(fname[:-1]).readlines()) 218 for essid, wi in to_resolve: 219 if not groups.has_key(essid): 220 print "Warning: node %s, %s refers to unknown essid %s" % (wi.node.name, wi.name, essid) 221 continue 222 groups[essid].add_wi(wi) 223 for group in groups.values(): 224 group.uniq() 34 for fname in open('l').readlines(): 35 parse_wleiden_conf(open(fname[:-1]).readlines()) 225 36 226 def parse_coupled(filename):227 try:228 for line in open(filename).readlines():229 supername, rest = line[:-1].split(':')230 subnodes = []231 for nodename in rest.split(' '):232 if nodename == '':233 continue234 node = nodes[nodename]235 del nodes[nodename]236 subnodes.append(node)237 node = SuperNode(supername, subnodes)238 nodes[supername] = node239 except:240 pass241 242 def parse_special(filename):243 for line in open(filename).readlines():244 fields = line[:-1].split(' ')245 nodename = fields[0]246 score = int(fields[1])247 channels = map(lambda c: int(c), fields[2:])248 nodes[nodename].setSpecialScoreForChannels(score, channels)249 250 # END UGLY PARSING CODE251 252 def plot_configuration(conf, out):253 out.write("digraph plot {\n")254 for essid in groups:255 out.write("\"%s\" [shape=box label=\"%s\\n(%d)\"]\n" % (essid, essid, conf[essid]))256 for nodename in nodes.keys():257 for wi in nodes[nodename].wis:258 if wi.group == None:259 continue260 out.write("\"%s\" -> \"%s\"\n" % (nodename, wi.group.name))261 out.write("}")262 263 parse_metafile('l')264 parse_coupled('coupled.conf')265 parse_special('special.conf')266 267 for essid in groups.keys():268 print essid, map(lambda wi: wi.node.name, groups[essid].wis)269 270 for i in range(20):271 conf = Configuration()272 conf.randomize()273 population.append(conf)274 275 last_high_score = -10000000276 iterations_since_new_high_score = 0277 while iterations_since_new_high_score < 1000:278 for i in range(0, 9):279 p = population[i].copy()280 #population[i].crossover(population[i + 10], random.randint(1, 4) * 2)281 population[i + 10] = p282 population[i + 10].mutate(0.05)283 population.sort(lambda a, b: cmp(b.score(), a.score()))284 high_score = population[0].score()285 if high_score > last_high_score:286 last_high_score = high_score287 iterations_since_new_high_score = 0288 iterations_since_new_high_score = iterations_since_new_high_score + 1289 print high_score290 plot_configuration(population[0].conf, open("foo.dot", 'w'))291 os.system('neato -Gstart=foo -Goverlap=false/scale -Gsplines=true -Gsep=2 -Gratio=fill -Gnslimit=50.0 -Grotate=90 -Gsize="11,7.5" -Tps -o channelga.ps foo.dot')292
Note:
See TracChangeset
for help on using the changeset viewer.