Index: /nodes/channelga.ml =================================================================== --- /nodes/channelga.ml (revision 1979) +++ /nodes/channelga.ml (revision 1980) @@ -1,29 +1,5 @@ -(** - experiment met evolutionary programming voor de kanalenplanning - het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld - fout. wat er wel goed in zit is het parseren van de bestaande situatie en - het scoren van (nu random) configuraties. - - de score functie is nu redelijk simplistisch: - - de score van een combinatie van twee interfaces op een node is 1 als er - twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5 - als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn - - de score van een node is de som van de scores van alle combinaties van - interfaces van die node, maal het aantal interfaces. dat laatste omdat - een positieve score hebben knapper is met meer interfaces dan met minder, - dus dat moet beloond. een negatieve score is erger met meer interfaces - (belangrijker node, waarschijnlijk) dan met minder, dus dat moet - bestraft. - - de totale score is de som van de scores van de nodes - - het stukje "genetisch" aan het einde is afgeraffeld. mutation en - recombination gebeuren op de oplossing zelf ipv op een bitstring - representatie. selection is dom en neemt gewoon de helft beste oplossingen. - - lvoge@cs.vu.nl *) - (* a few constants *) let population_size = 20 -and max_stagnant_iterations = 1000 +and max_stagnant_iterations = 10000 and mutation_rate = 0.05;; @@ -58,4 +34,5 @@ (* given a hashtable, return all the values as a list *) let values t = Hashtbl.fold (fun k d a -> d::a) t [];; +let copyarray src dest = Array.blit src 0 dest 0 (Array.length src);; (* given a list, return a list of pairs with all possible combinations of @@ -86,9 +63,11 @@ let node_score c n = let foldfunc acc (wi1, wi2) = acc + (wi_score c wi1 wi2) in - List.fold_left foldfunc 0 (combinations n.node_wis);; + let base_score = List.fold_left foldfunc 0 (combinations n.node_wis) in + base_score * (List.length n.node_wis);; let score_configuration c (ns: node list) = let foldfunc acc n = acc + (node_score (Hashtbl.find c) n) in - List.fold_left foldfunc 0 ns;; + let nodescores = List.fold_left foldfunc 0 ns in + nodescores;; (* given a filename, return a list of all the lines in the file with the given @@ -111,7 +90,4 @@ with Not_found -> let group = { group_essid = gname; group_wis = [ new_wi ] } in - print_string "added group "; - print_string gname; - print_newline(); Hashtbl.add groups gname group in new_wi @@ -133,14 +109,20 @@ ;; +(** Return a random configuration. For some reason, if this function accesses + the global 'groups' hash instead of getting it passed in from above, that + hash is empty. *) let random_configuration groups = let conf = Hashtbl.create 30 in - Hashtbl.iter (fun k d -> Hashtbl.add conf k (1 + (Random.int 12))) groups; + Hashtbl.iter (fun k _ -> Hashtbl.add conf k (1 + (Random.int 12))) groups; conf (* Mutate the configuration in the given population at the given offset *) let mutate p i = - Hashtbl.iter (fun essid chan -> let f = Random.float 1.0 in - if (f < mutation_rate) then - Hashtbl.replace p.(i) essid (1 + (Random.int 13))) p.(i);; + Hashtbl.iter (fun essid _ -> let f = Random.float 1.0 in + let group = Hashtbl.find groups essid in + let maxchannel = if (List.length group.group_wis) == 1 then 11 + else 13 in + if (f < mutation_rate) then + Hashtbl.replace p.(i) essid (1 + (Random.int maxchannel))) p.(i);; let print_conf conf = @@ -150,6 +132,24 @@ List.iter (fun n -> print_string (n.node_name ^ ":" ^ (wis n) ^ "\n")) sorted_nodes +let parse_nodeclusters fname = + let spacere = Str.regexp " " in + (* handle a row of fields. the first field is the supernode name, the + rest are the subnode names. create a new node for the supernode, + stuff all the wi's of the subnodes under it, names prefixed with + their original node's names for clarity, and remove the subnodes + from the nodes hashtable *) + let do_fields f = let nodename = head f in + let subnodenames = tail f in + let subnodes = List.map (Hashtbl.find nodes) subnodenames in + List.iter (Hashtbl.remove nodes) subnodenames; + let prefixed_wis n = List.map (fun w -> { w with wi_name = n.node_name ^ "." ^ w.wi_name}) n.node_wis in + let wis = List.fold_left (fun a s -> a@(prefixed_wis s)) [] subnodes in + let node = { node_name = nodename; node_wis = wis } in + Hashtbl.add nodes nodename node in + List.iter (do_fields $ (Str.split spacere)) (snarf_lines fname);; + let main = parse_file Sys.argv.(1); + parse_nodeclusters "coupled.conf"; Random.self_init(); let population = Array.init population_size (fun _ -> random_configuration groups) in @@ -170,5 +170,6 @@ (* sort on the first field *) Array.sort (fun x y -> compare (fst y) (fst x)) score_pop; - Array.blit (Array.map snd score_pop) 0 population 0 (Array.length score_pop); + (* extract the, now sorted, configuration and put it into population *) + copyarray (Array.map snd score_pop) population; (* now look at the best score and update the highscore if necessary *) Index: /nodes/channelga.mli =================================================================== --- /nodes/channelga.mli (revision 1980) +++ /nodes/channelga.mli (revision 1980) @@ -0,0 +1,72 @@ +(** + experiment met evolutionary programming voor de kanalenplanning + het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld + fout. wat er wel goed in zit is het parseren van de bestaande situatie en + het scoren van (nu random) configuraties. + + de score functie is nu redelijk simplistisch: + - de score van een combinatie van twee interfaces op een node is 1 als er + twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5 + als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn + - de score van een node is de som van de scores van alle combinaties van + interfaces van die node, maal het aantal interfaces. dat laatste omdat + een positieve score hebben knapper is met meer interfaces dan met minder, + dus dat moet beloond. een negatieve score is erger met meer interfaces + (belangrijker node, waarschijnlijk) dan met minder, dus dat moet + bestraft. + - de totale score is de som van de scores van de nodes + + het stukje "genetisch" aan het einde is afgeraffeld. mutation en + recombination gebeuren op de oplossing zelf ipv op een bitstring + representatie. selection is dom en neemt gewoon de helft beste oplossingen. + + lvoge@cs.vu.nl *) + +(** How large a population should the system maintain *) +val population_size : int +(** The maximum number of iterations to try to improve *) +val max_stagnant_iterations : int +(** The chance a solution element (channel assignment) will change *) +val mutation_rate : float + +type wi = { + wi_name : string; + wi_nodename : string; + wi_essid : string; +} +and group = { group_essid : string; mutable group_wis : wi list; } +and node = { node_name : string; node_wis : wi list; } + +(** Global hashtable mapping from nodename to node record *) +val nodes : (string, node) Hashtbl.t +(** Global hashtable mapping from essid to group record *) +val groups : (string, group) Hashtbl.t + +(** Given two functions, return the composition of these functions *) +val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b +(** Shorthand for compose *) +val ( $ ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b +(** Shorthand for List.hd *) +val head : 'a list -> 'a +(** Shorthand for List.tl *) +val tail : 'a list -> 'a list +val maketuple : 'a -> 'b -> 'a * 'b +(** Given a hashtable, return a list of its keys *) +val keys : ('a, 'b) Hashtbl.t -> 'a list +(** Given a hashtable, return a list of its values *) +val values : ('a, 'b) Hashtbl.t -> 'b list +(** Copy the given array into the other given array *) +val copyarray : 'a array -> 'a array -> unit +(** Given a list, return a list of pairs of all combinations of elements from the given list *) +val combinations : 'a list -> ('a * 'a) list +val wi_score : (string -> int) -> wi -> wi -> int +val node_score : (string -> int) -> node -> int +val score_configuration : (string, int) Hashtbl.t -> node list -> int +val snarf_lines : string -> string list +val parse_pair : string -> string * string -> wi +val parse_fields : string list -> unit +val parse_file : string -> unit +val random_configuration : ('a, 'b) Hashtbl.t -> ('a, int) Hashtbl.t +val mutate : (string, int) Hashtbl.t array -> int -> unit +val print_conf : (string, int) Hashtbl.t -> unit +val main : unit Index: /nodes/prepconf.py =================================================================== --- /nodes/prepconf.py (revision 1980) +++ /nodes/prepconf.py (revision 1980) @@ -0,0 +1,36 @@ +# gegeven een file met een lijst van te gebruiken wleiden.conf's, print +# op stdout een file waar channelga.ml wat mee kan. +import re + +def parse_wleiden_conf(lines): + essid = None + wi = None + for l in lines: + if wi != None: + match = re.match("^ESSID=(.*)", l) + if match != None: + print match.group(1), + match = re.match("^EW[0-9]*", l) + if match != None: + wi = None + essid = None + match = re.match("^EOS", l) + if match != None: + wi = None + essid = None + else: + match = re.match("^\$nodename='([^']*)';.*", l) + if match != None: + print "" + print match.group(1).lower(), + match = re.match("^\$config{'wi[0-9]*:[0-9].*", l) + if match != None: + continue + match = re.match("^\$config{'(wi[0-9]*).*", l) + if match != None: + print match.group(1).lower(), + wi = 1 + +for fname in open('l').readlines(): + parse_wleiden_conf(open(fname[:-1]).readlines()) +