Changeset 1980 in genesis


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
Location:
nodes
Files:
1 added
1 edited
1 copied

Legend:

Unmodified
Added
Removed

  • nodes/channelga.ml

    r1979 r1980  
    1 (**
    2   experiment met evolutionary programming voor de kanalenplanning
    3   het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld
    4   fout. wat er wel goed in zit is het parseren van de bestaande situatie en
    5   het scoren van (nu random) configuraties.
    6 
    7   de score functie is nu redelijk simplistisch:
    8     - de score van een combinatie van twee interfaces op een node is 1 als er
    9       twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5
    10       als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn
    11     - de score van een node is de som van de scores van alle combinaties van
    12       interfaces van die node, maal het aantal interfaces. dat laatste omdat
    13       een positieve score hebben knapper is met meer interfaces dan met minder,
    14       dus dat moet beloond. een negatieve score is erger met meer interfaces
    15       (belangrijker node, waarschijnlijk) dan met minder, dus dat moet
    16       bestraft.
    17     - de totale score is de som van de scores van de nodes
    18 
    19   het stukje "genetisch" aan het einde is afgeraffeld. mutation en
    20   recombination gebeuren op de oplossing zelf ipv op een bitstring
    21   representatie. selection is dom en neemt gewoon de helft beste oplossingen.
    22 
    23   lvoge@cs.vu.nl *)
    24 
    251(* a few constants *)
    262let population_size = 20
    27 and max_stagnant_iterations = 1000
     3and max_stagnant_iterations = 10000
    284and mutation_rate = 0.05;;
    295
    … …  
    5834(* given a hashtable, return all the values as a list *)
    5935let values t = Hashtbl.fold (fun k d a -> d::a) t [];;
     36let copyarray src dest = Array.blit src 0 dest 0 (Array.length src);;
    6037
    6138(* given a list, return a list of pairs with all possible combinations of
    … …  
    8663let node_score c n =
    8764        let foldfunc acc (wi1, wi2) = acc + (wi_score c wi1 wi2) in
    88         List.fold_left foldfunc 0 (combinations n.node_wis);;
     65        let base_score = List.fold_left foldfunc 0 (combinations n.node_wis) in
     66        base_score * (List.length n.node_wis);;
    8967
    9068let score_configuration c (ns: node list) =
    9169        let foldfunc acc n = acc + (node_score (Hashtbl.find c) n) in
    92         List.fold_left foldfunc 0 ns;;
     70        let nodescores = List.fold_left foldfunc 0 ns in
     71        nodescores;;
    9372
    9473(* given a filename, return a list of all the lines in the file with the given
    … …  
    11190                  with Not_found ->
    11291                        let group = { group_essid = gname; group_wis = [ new_wi ] } in
    113                         print_string "added group ";
    114                         print_string gname;
    115                         print_newline();
    11692                        Hashtbl.add groups gname group in
    11793        new_wi
    … …  
    133109        ;;
    134110
     111(** Return a random configuration. For some reason, if this function accesses
     112  the global 'groups' hash instead of getting it passed in from above, that
     113  hash is empty. *)
    135114let random_configuration groups =
    136115        let conf = Hashtbl.create 30 in
    137         Hashtbl.iter (fun k d -> Hashtbl.add conf k (1 + (Random.int 12))) groups;
     116        Hashtbl.iter (fun k _ -> Hashtbl.add conf k (1 + (Random.int 12))) groups;
    138117        conf
    139118
    140119(* Mutate the configuration in the given population at the given offset *)
    141120let mutate p i =
    142         Hashtbl.iter (fun essid chan -> let f = Random.float 1.0 in
    143                                         if (f < mutation_rate) then
    144                                           Hashtbl.replace p.(i) essid (1 + (Random.int 13))) p.(i);;
     121        Hashtbl.iter (fun essid _ -> let f = Random.float 1.0 in
     122                                     let group = Hashtbl.find groups essid in
     123                                     let maxchannel = if (List.length group.group_wis) == 1 then 11
     124                                                      else 13 in
     125                                     if (f < mutation_rate) then
     126                                             Hashtbl.replace p.(i) essid (1 + (Random.int maxchannel))) p.(i);;
    145127
    146128let print_conf conf =
    … …  
    150132        List.iter (fun n -> print_string (n.node_name ^ ":" ^ (wis n) ^ "\n")) sorted_nodes
    151133
     134let parse_nodeclusters fname =
     135        let spacere = Str.regexp " " in
     136        (* handle a row of fields. the first field is the supernode name, the
     137           rest are the subnode names. create a new node for the supernode,
     138           stuff all the wi's of the subnodes under it, names prefixed with
     139           their original node's names for clarity, and remove the subnodes
     140           from the nodes hashtable *)
     141        let do_fields f = let nodename = head f in
     142                          let subnodenames = tail f in
     143                          let subnodes = List.map (Hashtbl.find nodes) subnodenames in
     144                          List.iter (Hashtbl.remove nodes) subnodenames;
     145                          let prefixed_wis n = List.map (fun w -> { w with wi_name = n.node_name ^ "." ^ w.wi_name}) n.node_wis in
     146                          let wis = List.fold_left (fun a s -> a@(prefixed_wis s)) [] subnodes in
     147                          let node = { node_name = nodename; node_wis = wis } in
     148                          Hashtbl.add nodes nodename node in
     149        List.iter (do_fields $ (Str.split spacere)) (snarf_lines fname);;
     150
    152151let main =
    153152        parse_file Sys.argv.(1);
     153        parse_nodeclusters "coupled.conf";
    154154        Random.self_init();
    155155        let population = Array.init population_size (fun _ -> random_configuration groups) in
    … …  
    170170                (* sort on the first field *)
    171171                Array.sort (fun x y -> compare (fst y) (fst x)) score_pop;
    172                 Array.blit (Array.map snd score_pop) 0 population 0 (Array.length score_pop);
     172                (* extract the, now sorted, configuration and put it into population *)
     173                copyarray (Array.map snd score_pop) population;
    173174                (* now look at the best score and update the highscore if
    174175                   necessary *)

  • 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.