Changeset 1980 in genesis for nodes/channelga.ml
- Timestamp:
- Apr 11, 2004, 2:01:11 AM (21 years ago)
- File:
-
- 1 edited
-
nodes/channelga.ml (modified) (7 diffs)
Legend:
- Unmodified
- Added
- Removed
-
nodes/channelga.ml
r1979 r1980 1 (**2 experiment met evolutionary programming voor de kanalenplanning3 het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld4 fout. wat er wel goed in zit is het parseren van de bestaande situatie en5 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 er9 twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -510 als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn11 - de score van een node is de som van de scores van alle combinaties van12 interfaces van die node, maal het aantal interfaces. dat laatste omdat13 een positieve score hebben knapper is met meer interfaces dan met minder,14 dus dat moet beloond. een negatieve score is erger met meer interfaces15 (belangrijker node, waarschijnlijk) dan met minder, dus dat moet16 bestraft.17 - de totale score is de som van de scores van de nodes18 19 het stukje "genetisch" aan het einde is afgeraffeld. mutation en20 recombination gebeuren op de oplossing zelf ipv op een bitstring21 representatie. selection is dom en neemt gewoon de helft beste oplossingen.22 23 lvoge@cs.vu.nl *)24 25 1 (* a few constants *) 26 2 let population_size = 20 27 and max_stagnant_iterations = 1000 3 and max_stagnant_iterations = 10000 28 4 and mutation_rate = 0.05;; 29 5 … … 58 34 (* given a hashtable, return all the values as a list *) 59 35 let values t = Hashtbl.fold (fun k d a -> d::a) t [];; 36 let copyarray src dest = Array.blit src 0 dest 0 (Array.length src);; 60 37 61 38 (* given a list, return a list of pairs with all possible combinations of … … 86 63 let node_score c n = 87 64 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);; 89 67 90 68 let score_configuration c (ns: node list) = 91 69 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;; 93 72 94 73 (* given a filename, return a list of all the lines in the file with the given … … 111 90 with Not_found -> 112 91 let group = { group_essid = gname; group_wis = [ new_wi ] } in 113 print_string "added group ";114 print_string gname;115 print_newline();116 92 Hashtbl.add groups gname group in 117 93 new_wi … … 133 109 ;; 134 110 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. *) 135 114 let random_configuration groups = 136 115 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; 138 117 conf 139 118 140 119 (* Mutate the configuration in the given population at the given offset *) 141 120 let 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);; 145 127 146 128 let print_conf conf = … … 150 132 List.iter (fun n -> print_string (n.node_name ^ ":" ^ (wis n) ^ "\n")) sorted_nodes 151 133 134 let 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 152 151 let main = 153 152 parse_file Sys.argv.(1); 153 parse_nodeclusters "coupled.conf"; 154 154 Random.self_init(); 155 155 let population = Array.init population_size (fun _ -> random_configuration groups) in … … 170 170 (* sort on the first field *) 171 171 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; 173 174 (* now look at the best score and update the highscore if 174 175 necessary *)
Note:
See TracChangeset
for help on using the changeset viewer.
