Changeset 1980 in genesis for nodes/prepconf.py


Ignore:
Timestamp:
Apr 11, 2004, 2:01:11 AM (21 years ago)
Author:
lodewijk
Message:
  • oops, prepconf.py vergeten te committen. maakt van een lijst van wleiden.conf paden een invoer file voor channelga.ml
  • het supernode concept geport, een virtuele node met een stel echte nodes als kinderen waarvan de interfaces bij elkaar worden genomen (cetim1, 2 & 3 bv)
  • interface file erbij met begin van documentatie
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.
    233import re
    24 import random
    25 import os
    26 
    27 # deze twee zijn nodig voor de evaluatie van een configuratie
    28 nodes = {}              # nodename -> Node
    29 groups = {}             # essid -> WIGroup
    30 
    31 population = []
    32 
    33 # gegeven een lijst, geef de lijst zonder dubbele elementen
    34 def uniq(l):
    35         d = {}
    36         for e in l:
    37                 d[e] = 1
    38         return d.keys()
    39 
    40 class Node:
    41         def __init__(self, name, wis):
    42                 self.name = name
    43                 self.wis = wis
    44                 self.special = {}
    45                 for wi in wis:
    46                         wi.setNode(self)
    47         def score(self):
    48                 score = 0
    49                 for i in range(len(self.wis)):
    50                         wi_i = self.wis[i]
    51                         if wi_i.group == None:
    52                                 # orphaned interface
    53                                 continue
    54                         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                                                 continue
    61                                         diff = abs(wi_i.group.channel - wi_j.group.channel)
    62                                         if diff > 2:
    63                                                 score = score + 1
    64                                         elif diff == 2:
    65                                                 score = score - 1
    66                                         elif diff == 1:
    67                                                 score = score - 5
    68                                         else:
    69                                                 score = score - 10
    70                         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 score
    74         def setSpecialScoreForChannels(self, score, channels):
    75                 for c in channels:
    76                         self.special[c] = score
    77 
    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 = name
    82                 self.nodes = nodes
    83                 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 = name
    91                 self.node = None
    92                 self.group = None
    93                 self.omni = 0
    94         def setNode(self, node):
    95                 self.node = node
    96         def setGroup(self, group):
    97                 self.group = group
    98 
    99 class WIGroup:
    100         def __init__(self, name):
    101                 self.name = name
    102                 self.wis = []
    103                 self.channel = None
    104         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. aangezien
    111 # groepen keyed zijn op essid is de concrete configuratie hier een dict van
    112 # essids naar kanalen.
    113 class Configuration:
    114         def __init__(self):
    115                 self.conf = None
    116                 self.calculated_score = None
    117         def copy(self):
    118                 c = Configuration()
    119                 c.conf = self.conf.copy()
    120                 c.calculated_score = None
    121                 return c
    122         def randomize(self):
    123                 self.conf = {}
    124                 for essid in groups.keys():
    125                         self.conf[essid] = random.randint(1, 13)
    126                 self.calculated_score = None
    127         def score(self):
    128                 assert len(self.conf) == len(groups)
    129                 if self.calculated_score != None:
    130                         return self.calculated_score
    131                 for essid in groups.keys():
    132                         groups[essid].channel = self.conf[essid]
    133                 score = 0
    134                 for node in nodes.values():
    135                         score = score + node.score()
    136                 self.calculated_score = score
    137                 return score
    138         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 points
    144                 essids = groups.keys()
    145                 points = [random.randint(0, len(essids) - 1) for i in range(numpoints)]
    146                 points.sort()
    147                 conf = {}
    148                 who = 0
    149                 lastpoint = 0
    150                 while len(points):
    151                         point = points.pop(0)
    152                         if who == 0:
    153                                 d = self.conf
    154                         else:
    155                                 d = partner.conf
    156                         who = 1 - who
    157                         for i in range(lastpoint, point + 1):
    158                                 conf[essids[i]] = d[essids[i]]
    159                         lastpoint = point
    160                 if who == 0:
    161                         d = self.conf
    162                 else:
    163                         d = partner.conf
    164                 for i in range(lastpoint, len(essids)):
    165                         conf[essids[i]] = d[essids[i]]
    166                 assert len(conf) == len(groups)
    167                 self.conf = conf
    168 
    169 
    170 # BEGIN UGLY PARSING CODE
    171 
    172 to_resolve = []         # list of (essid, WI) tuples
    1734
    1745def parse_wleiden_conf(lines):
    1756        essid = None
    1767        wi = None
    177         wis = []
    1788        for l in lines:
    1799                if wi != None:
    180                         match = re.match("^MODE=master.*", l)
    181                         if match != None:
    182                                 master = 1
    18310                        match = re.match("^ESSID=(.*)", l)
    18411                        if match != None:
    185                                 essid = match.group(1)
     12                                print match.group(1),
    18613                        match = re.match("^EW[0-9]*", l)
    18714                        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:
    19619                                wi = None
    19720                                essid = None
    … …  
    19922                        match = re.match("^\$nodename='([^']*)';.*", l)
    20023                        if match != None:
    201                                 nodename = match.group(1).lower()
     24                                print ""
     25                                print match.group(1).lower(),
    20226                        match = re.match("^\$config{'wi[0-9]*:[0-9].*", l)
    20327                        if match != None:
    … …  
    20529                        match = re.match("^\$config{'(wi[0-9]*).*", l)
    20630                        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
    21233
    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()
     34for fname in open('l').readlines():
     35        parse_wleiden_conf(open(fname[:-1]).readlines())
    22536
    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                                         continue
    234                                 node = nodes[nodename]
    235                                 del nodes[nodename]
    236                                 subnodes.append(node)
    237                         node = SuperNode(supername, subnodes)
    238                         nodes[supername] = node
    239         except:
    240                 pass
    241 
    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 CODE
    251 
    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                                 continue
    260                         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 = -10000000
    276 iterations_since_new_high_score = 0
    277 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] = p
    282                 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_score
    287                 iterations_since_new_high_score = 0
    288         iterations_since_new_high_score = iterations_since_new_high_score + 1
    289         print high_score
    290 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.