Changeset 1990 in genesis for nodes/channelga.ml

Timestamp:

Apr 12, 2004, 12:01:27 AM (21 years ago)

Author:

lodewijk

Message:

prutsen met channelga.ml

File:

• nodes/channelga.ml (modified) (8 diffs)

nodes/channelga.ml

@@ -1 @@
-(* a few constants *)
-let population_size = 20
+(**
+  Experimental channel assigning program using an evolutionary algorithm.
+
+  The scoring function is simple:
+    - the score of a combination of two interfaces is 1 if there's two or more
+      channels between them, -1 if there's 1 channel between them, -5 if
+      there's no channels between them (they're on adjacent channels) and -10
+      if they're on the same channel
+    - the score for a node is the sum of the scores of all the combinations of
+      interfaces for that node, minus any node-specific penalties (eg.
+      channels 7, 8 and 9 are unusable and score -1000 on node x), scaled by
+      the number of interfaces to give more weight to larger nodes (the
+      assumption being that larger nodes are more important nodes)
+    - the total score of the network is the sum of the score of the nodes,
+      minus any network-wide penalties (eg. the omni's for node x and node y
+      can see eachother, so they should be apart)
+
+ - install an O'Caml compiler. /usr/ports/lang/ocaml/ in FreeBSD, ocaml in
+   Debian.
+
+ - compile with
+  
+    $ ocamlopt -o foo str.cmxa channelga.ml
+
+ - run with
+
+   $ ./foo f
+
+ where f is the result of running prepconf.py on a file with a list of 
+ paths to the wleiden.conf's to consider.
+*)
+
+(* a few constants suitable for twiddling *)
+(** How large a population should the system maintain? *)
+let population_size = 100
+(** How long should the system iterate after an improvement? *)
 and max_stagnant_iterations = 10000
-and mutation_rate = 0.05;;
+(** What is the chance for an ESSID to channel assignment to mutate to a 
+    random channel? *)
+and mutation_rate = 0.1;;
 
 (* the type definitions. note that Caml has trouble with mutually recursive
@@ -20 +56 @@
         node_wis: wi list;
 };;
-
-let nodes = Hashtbl.create 4;;
-let groups = Hashtbl.create 4;;
+(** A configuration is an assignment of groups, identified by essid, to a
+    channel, plus a score. The code should be careful not to use the score
+    between mutating an re-evaluating. *)
+type configuration = {
+        mutable score: int;
+        conf: (string, int) Hashtbl.t;
+};;
+type 'a maybe = Nothing | Just of 'a;;
+
+(** The global nodes hash, mapping from node name to node struct. *)
+let nodes = Hashtbl.create 4
+(** The global groups hash, mapping from essid to group struct. *)
+let groups = Hashtbl.create 4
 
 (* some convenience functions *)
-let compose f g = fun x -> f(g(x));;
-let ($) = compose;;
-let maketuple a b = (a, b);;
-let head = List.hd;;
-let tail = List.tl;;
-(* given a hashtable, return all the keys as a list *)
-let keys t = Hashtbl.fold (fun k d a -> k::a) t [];;
-(* 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 
+
+(** Function composition. *)
+let compose f g = fun x -> f(g(x))
+let ($) = compose
+(** Turn two individual values into a tuple *)
+let maketuple a b = (a, b)
+(** Shorthand for List.hd *)
+let head = List.hd
+(** Shorthand for List.tail *)
+let tail = List.tl
+let just x = match x with
+               Nothing -> assert false
+             | Just s -> s
+(** Given a hashtable, return all the keys as a list *)
+let keys t = Hashtbl.fold (fun k d a -> k::a) t []
+(** Given a hashtable, return all the values as a list *)
+let values t = Hashtbl.fold (fun k d a -> d::a) t []
+(** Copy one array into the other *)
+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 
    items from the given list *)
 let rec combinations l =
         match l with
           []    -> []
-        | x::xs -> (List.map (maketuple x) xs)@(combinations xs);;
-
-(* given a configuration and two wi's, return the score *)
+        | x::xs -> (List.map (maketuple x) xs)@(combinations xs)
+
+(** Given a configuration and two wi's, return the score *)
 let wi_score c wi1 wi2 =
         let scoretable = [ ((<=) 2,  1);
@@ -58 +113 @@
         runtable scoretable;;
 
-(* given a configuration and a node, return the score. this is simply the sum of
+(** Given a configuration and a node, return the score. this is simply the sum of
    the scores of all the combinations of interfaces, written down as a fold for
    efficiency *)
@@ -64 +119 @@
         let foldfunc acc (wi1, wi2) = acc + (wi_score c wi1 wi2) in
         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) =
+        base_score * (List.length n.node_wis)
+
+(** Given a list of nodes and a configuration, return the score for the whole
+    configuration. This is the sum of the scores for all nodes. *)
+let score_configuration ns c =
         let foldfunc acc n = acc + (node_score (Hashtbl.find c) n) in
         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
+        nodescores
+
+(** Given a filename, return a list of all the lines in the file with the given
    filename *)
 let snarf_lines fname =
@@ -83 +140 @@
         with End_of_file -> !result
 
-let parse_pair nodename (wname, gname) = 
-        let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = gname} in
+(** Given the name of the node currently being parsed, parse the given tuple
+    that consists of a wi name and an essid. *)
+let parse_pair nodename (wname, essid) = 
+        let new_wi = { wi_name = wname; wi_nodename = nodename; wi_essid = essid} in
         let foo = try
-                        let group = Hashtbl.find groups gname in
+                        let group = Hashtbl.find groups essid in
                         group.group_wis <- new_wi::group.group_wis;
                   with Not_found ->
-                        let group = { group_essid = gname; group_wis = [ new_wi ] } in
-                        Hashtbl.add groups gname group in
+                        let group = { group_essid = essid; group_wis = [ new_wi ] } in
+                        Hashtbl.add groups essid group in
         new_wi
 
@@ -112 +171 @@
   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 _ -> 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 _ -> 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 random_configuration groups evaluate =
+        let h = Hashtbl.create 30 in
+        Hashtbl.iter (fun k _ -> Hashtbl.add h k (1 + (Random.int 12))) groups;
+        { score = (evaluate h); conf = h }
 
 let print_conf conf = 
@@ -149 +199 @@
         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
-        let last_high_score = ref (-1000000) in
+(** Generalized evolutionary algorithm driver. 
+      initialize: () -> configuration array
+      recombine:
+      mutate: configuration array -> configuration array
+      evaluate: configuration array -> configuration array
+      select: configuration array -> configuration array
+      
+    and the result is the best configuration *)
+let evolutionary_algorithm initialize recombine mutate evaluate select = 
+        let population = (evaluate $ initialize) () in
+        let last_high_score = ref population.(0).score in
         let iterations_since_new_high_score = ref 0 in
         let generation = ref 0 in
         let all_nodes = values nodes in
-        while !iterations_since_new_high_score < max_stagnant_iterations do
-                (* mutate the population *)
-                for i = 0 to (population_size / 2 - 1) do
-                        let i2 = i + population_size / 2 in
-                        population.(i2) <- Hashtbl.copy population.(i);
-                        mutate population (i2)
-                done;
-                (* sort the populations according to score. to do this, make
-                   a list of (score, solution) tuples *)
-                let score_pop = Array.map (fun c -> ((score_configuration c all_nodes), c)) population in
-                (* sort on the first field *)
-                Array.sort (fun x y -> compare (fst y) (fst x)) 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 *)
-                let high_score = fst score_pop.(0) in
+        let _ = while !iterations_since_new_high_score < max_stagnant_iterations do
+                let newpop = (recombine $ mutate $ evaluate $ select) population in
+                Array.sort (fun a b -> compare b.score a.score) newpop;
+                copyarray newpop population;
+                let high_score = population.(0).score in
                 if high_score > !last_high_score then begin
                         last_high_score := high_score;
@@ -188 +231 @@
                 incr iterations_since_new_high_score;
                 incr generation
-        done;
-        print_conf population.(0);;
+        done in
+        population.(0);;
+
+let main = 
+        parse_file Sys.argv.(1);
+        parse_nodeclusters "coupled.conf";
+        Random.self_init();
+        let all_nodes = values nodes in
+        let evaluate_hash = score_configuration all_nodes in
+        let initialize () = Array.init population_size (fun _ -> random_configuration groups evaluate_hash) in
+        let recombine x = x in
+        let mutate_conf conf =
+                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 conf essid (1 + (Random.int maxchannel))) conf in
+        let mutate population = let mutants = Array.map (fun c -> let hash = Hashtbl.copy c.conf in
+                                                                  mutate_conf hash;
+                                                                  { score = evaluate_hash hash;
+                                                                    conf = hash}) population in
+                                Array.append population mutants in
+        let evaluate population = Array.iter (fun c -> c.score <- evaluate_hash c.conf) population;
+                                  population in
+        let select p = Array.sub p 0 ((Array.length p) / 2) in
+        let best = evolutionary_algorithm initialize recombine mutate evaluate select in
+        print_conf best.conf;;
 
 main