Here is the base patch for the genetic-library.
It includes generic routines for modifying and manipulating genes of
children. If a specific routine is needed, that can be used instead.
Signed-off-by: Jake Moilanen <[EMAIL PROTECTED]>
Change Log
0.2 1/12/2004
- Added ability to run multiple fitness functions that work on
specific genes by using phenotypes.
- Added a post calc fitness to use for normalization of various
fitness routines.
- Restructured /proc tree.
- Made a separate snapshot call instead of doing it in set_genes.
- Rework the mutation code, to do it as a rate of the total number of
genes instead of an arbitrary number.
0.1 1/7/2004
- Added ability for mutates to take iterative steps.
- Moved debug info to a /proc file.
- Added a mutate_rate_change. The rate of mutation will increase when
fitness goes down. Hopefully allowing it to optimize for new workloads.
- Added a boot option for disabling the genetic lib.
- Had it randomly determined which parent a gene came from.
---
diff -puN fs/proc/proc_misc.c~genetic-lib fs/proc/proc_misc.c
--- linux-2.6.10/fs/proc/proc_misc.c~genetic-lib Fri Jan 28 15:49:40 2005
+++ linux-2.6.10-moilanen/fs/proc/proc_misc.c Tue Feb 15 12:06:49 2005
@@ -38,6 +38,7 @@
#include <linux/smp_lock.h>
#include <linux/seq_file.h>
#include <linux/times.h>
+#include <linux/genetic.h>
#include <linux/profile.h>
#include <linux/blkdev.h>
#include <linux/hugetlb.h>
@@ -238,6 +239,97 @@ static int meminfo_read_proc(char *page,
return proc_calc_metrics(page, start, off, count, eof, len);
#undef K
}
+
+#ifdef CONFIG_GENETIC_LIB
+extern struct proc_dir_entry * genetic_root_dir;
+
+int genetic_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ int n = 0;
+ genetic_t * genetic = (genetic_t *)data;
+
+ struct list_head * p;
+ phenotype_t * pt;
+
+
+ n = sprintf(page, "%s:\n", genetic->name);
+ n += sprintf(page+n, "generation_number:\t\t%ld\n",
genetic->generation_number);
+ n += sprintf(page+n, "num_children:\t\t\t%ld\n", genetic->num_children);
+ n += sprintf(page+n, "child_life_time:\t\t%ld\n\n",
genetic->child_life_time);
+ n += sprintf(page+n, "child_number:\t\t\t%ld\n\n", genetic->child_number);
+
+ n += sprintf(page+n, "Phenotypes Average Fitness\n");
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ n += sprintf(page+n, "%-24s:\t\t%lld\n", pt->name, pt->avg_fitness);
+ }
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+
+int genetic_phenotype_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ int i;
+ int n = 0;
+ phenotype_t * pt = (phenotype_t *)data;
+
+ n = sprintf(page, "------ %s -----\n", pt->name);
+ n += sprintf(page+n, "generation_number:\t%ld\n",
pt->genetic->generation_number);
+ n += sprintf(page+n, "num_children:\t\t%ld\n\n", pt->num_children);
+ n += sprintf(page+n, "child_number:\t\t%ld\n", pt->child_number);
+ n += sprintf(page+n, "mutation_rate:\t\t%ld\n", pt->mutation_rate);
+ n += sprintf(page+n, "num_mutations:\t\t%ld\n", pt->num_mutations);
+ n += sprintf(page+n, "num_genes:\t\t%ld\n", pt->num_genes);
+ n += sprintf(page+n, "uid:\t\t\t%ld\n", pt->uid);
+ n += sprintf(page+n, "avg_fitness:\t\t%lld\n", pt->avg_fitness);
+ n += sprintf(page+n, "last_gen_avg_fitness:\t%lld\n",
pt->last_gen_avg_fitness);
+
+ n += sprintf(page+n, "\nFitness history\n");
+
+ for (i = pt->genetic->generation_number > GENETIC_HISTORY_SIZE ?
GENETIC_HISTORY_SIZE
+ : pt->genetic->generation_number-1; i > 0; i--)
+ n += sprintf(page+n, "%ld:\t%lld\n",
+ pt->genetic->generation_number - i,
+ pt->fitness_history[(pt->fitness_history_index - i) &
GENETIC_HISTORY_MASK]);
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+
+#if GENETIC_DEBUG
+int genetic_debug_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ int i, j, k;
+ int n = 0;
+ phenotype_t * pt = (phenotype_t *)data;
+
+ n = sprintf(page, "generation_number:\t%ld\n",
pt->genetic->generation_number);
+
+ for (i = 0, j = 1; i < pt->debug_size; j++) {
+ /* print out child number, and ID */
+ n += sprintf(page+n, "%d (%lld):", j, pt->debug_history[i++]);
+ /* print out child fitness */
+ n += sprintf(page+n, " %-12lld:\t", pt->debug_history[i++]);
+
+ for (k = 0; k < pt->child_ranking[0]->num_genes; k++) {
+ n += sprintf(page+n, "%lld\t", pt->debug_history[i++]);
+ }
+ n += sprintf(page+n, "\n");
+
+ if (j == pt->num_children) {
+ n += sprintf(page+n, "\n");
+ j = 0;
+ }
+ }
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+#endif /* GENETIC_DEBUG */
+#endif /* CONFIG_GENETIC_LIB */
extern struct seq_operations fragmentation_op;
static int fragmentation_open(struct inode *inode, struct file *file)
diff -puN /dev/null include/linux/genetic.h
--- /dev/null Fri Mar 14 06:52:15 2003
+++ linux-2.6.10-moilanen/include/linux/genetic.h Wed Feb 2 16:26:35 2005
@@ -0,0 +1,232 @@
+#ifndef __LINUX_GENETIC_H
+#define __LINUX_GENETIC_H
+/*
+ * include/linux/genetic.h
+ *
+ * Jake Moilanen <[EMAIL PROTECTED]>
+ * Copyright (C) 2004 IBM
+ *
+ * Genetic algorithm library
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <linux/list.h>
+#include <linux/timer.h>
+#include <linux/init.h>
+
+
+#define GENETIC_HISTORY_SIZE 0x8
+#define GENETIC_HISTORY_MASK (GENETIC_HISTORY_SIZE - 1)
+
+/* percentage of total number genes to mutate */
+#define GENETIC_DEFAULT_MUTATION_RATE 15
+
+/* XXX TODO Make this an adjustable runtime variable */
+/* Percentage that an iteration can jump within the range */
+#define GENETIC_ITERATIVE_MUTATION_RANGE 30
+
+/* the rate that GENETIC_DEFAULT_MUTATION_RATE itself can change */
+#define GENETIC_DEFAULT_MUTATION_RATE_CHANGE 4
+#define GENETIC_MAX_MUTATION_RATE 45
+#define GENETIC_MIN_MUTATION_RATE 10
+
+#define GENETIC_DEBUG 1
+#define GENETIC_NUM_DEBUG_POINTS 4
+
+#define GENETIC_PRINT_DEBUG 0
+#define gen_dbg(format, arg...) do { if (GENETIC_PRINT_DEBUG)
printk(KERN_EMERG __FILE__ ": " format "\n" , ## arg); } while (0)
+#define gen_trc(format, arg...) do { if (GENETIC_PRINT_DEBUG)
printk(KERN_EMERG __FILE__ ":%s:%d\n" , __FUNCTION__, __LINE__); } while (0)
+
+struct gene_param_s;
+struct genetic_s;
+struct phenotype_s;
+
+struct genetic_child_s {
+ struct list_head list;
+ long long fitness;
+ unsigned long num_genes;
+ void *genes;
+ struct gene_param_s *gene_param;
+ void *stats_snapshot;
+ int id;
+};
+
+typedef struct genetic_child_s genetic_child_t;
+
+/* Here's a generic idea of what it the genes could look like */
+struct gene_param_s {
+ unsigned long min;
+ unsigned long max;
+ unsigned long initial;
+ void (*mutate_gene)(genetic_child_t *, unsigned long);
+};
+
+typedef struct gene_param_s gene_param_t;
+
+struct phenotype_s {
+ struct list_head phenotype;
+
+ struct list_head children_queue[2];
+ struct list_head *run_queue;
+ struct list_head *finished_queue;
+ struct genetic_ops *ops;
+
+ char *name;
+
+ struct genetic_s *genetic; /* point back
+ * to genetic
+ * struct
+ */
+
+ unsigned long num_children; /* Must be power of 2
*/
+ unsigned long natural_selection_cutoff; /* How many children
+ * will survive
+ */
+ void *stats_snapshot;
+ unsigned long child_number;
+
+ /* percentage of total number of genes to mutate */
+ long mutation_rate;
+ unsigned long num_mutations;
+ unsigned long num_genes;
+
+ genetic_child_t **child_ranking;
+
+ void (*natural_selection)(struct phenotype_s *);
+
+ /* This UID is bitmap comprised of other phenotypes that contribute
+ to the genes */
+ unsigned long uid;
+
+ /* performance metrics */
+ long long avg_fitness;
+ long long last_gen_avg_fitness;
+
+ unsigned long fitness_history_index;
+ long long fitness_history[GENETIC_HISTORY_SIZE];
+
+#if GENETIC_DEBUG
+ unsigned long debug_size; /* number of longs in
+ debug history */
+ unsigned long debug_index;
+ long long *debug_history;
+#endif
+};
+
+typedef struct phenotype_s phenotype_t;
+
+struct genetic_s {
+ char *name;
+ struct timer_list timer;
+
+ struct list_head phenotype;
+
+ unsigned long child_number;
+ unsigned long child_life_time;
+ unsigned long num_children; /* Must be power of 2
*/
+
+ struct proc_dir_entry *dir;
+ struct proc_dir_entry *debug_dir;
+ unsigned long generation_number;
+
+};
+
+typedef struct genetic_s genetic_t;
+
+struct genetic_ops {
+ void (*create_child)(genetic_child_t *);
+ void (*set_child_genes)(void *);
+ void (*calc_fitness)(genetic_child_t *);
+ void (*combine_genes)(genetic_child_t *,
genetic_child_t *,
+ genetic_child_t *);
+ void (*mutate_child)(genetic_child_t *);
+ void (*calc_post_fitness)(phenotype_t *); /* Fitness
routine used when
+ * need to
take into account
+ * other
phenotype fitness
+ * results
after they ran
+ */
+ void (*take_snapshot)(phenotype_t *);
+ void (*shift_mutation_rate)(phenotype_t *);
+};
+
+/* Setup routines */
+int __init genetic_init(genetic_t ** in_genetic, unsigned long num_children,
+ unsigned long child_life_time,
+ char * name);
+int __init genetic_register_phenotype(genetic_t * genetic, struct genetic_ops
* ops,
+ unsigned long num_children, char * name,
+ unsigned long num_genes, unsigned long
uid);
+void __init genetic_start(genetic_t * genetic);
+
+/* Generic helper functions */
+void genetic_generic_mutate_child(genetic_child_t * child);
+void genetic_generic_iterative_mutate_gene(genetic_child_t * child, long
gene_num);
+void genetic_generic_combine_genes(genetic_child_t * parent_a,
+ genetic_child_t * parent_b,
+ genetic_child_t * child);
+void genetic_create_child_spread(genetic_child_t * child, unsigned long
num_children);
+void genetic_create_child_defaults(genetic_child_t * child);
+void genetic_general_shift_mutation_rate(phenotype_t * in_pt);
+
+#if BITS_PER_LONG >= 64
+
+static inline void divll(long long *n, long div, long *rem)
+{
+ *rem = *n % div;
+ *n /= div;
+}
+
+#else
+
+static inline void divl(int32_t high, int32_t low,
+ int32_t div,
+ int32_t *q, int32_t *r)
+{
+ int64_t n = (u_int64_t)high << 32 | low;
+ int64_t d = (u_int64_t)div << 31;
+ int32_t q1 = 0;
+ int c = 32;
+ while (n > 0xffffffff) {
+ q1 <<= 1;
+ if (n >= d) {
+ n -= d;
+ q1 |= 1;
+ }
+ d >>= 1;
+ c--;
+ }
+ q1 <<= c;
+ if (n) {
+ low = n;
+ *q = q1 | (low / div);
+ *r = low % div;
+ } else {
+ *r = 0;
+ *q = q1;
+ }
+ return;
+}
+
+static inline void divll(long long *n, long div, long *rem)
+{
+ int32_t low, high;
+ low = *n & 0xffffffff;
+ high = *n >> 32;
+ if (high) {
+ int32_t high1 = high % div;
+ int32_t low1 = low;
+ high /= div;
+ divl(high1, low1, div, &low, (int32_t *)rem);
+ *n = (int64_t)high << 32 | low;
+ } else {
+ *n = low / div;
+ *rem = low % div;
+ }
+}
+#endif
+
+#endif
diff -puN lib/Kconfig~genetic-lib lib/Kconfig
--- linux-2.6.10/lib/Kconfig~genetic-lib Fri Jan 28 15:49:40 2005
+++ linux-2.6.10-moilanen/lib/Kconfig Tue Feb 15 12:06:46 2005
@@ -30,6 +30,12 @@ config LIBCRC32C
require M here. See Castagnoli93.
Module will be libcrc32c.
+config GENETIC_LIB
+ bool "Genetic Library"
+ help
+ This option will build in a genetic library that will tweak
+ kernel parameters autonomically to improve performance.
+
#
# compression support is select'ed if needed
#
diff -puN lib/Makefile~genetic-lib lib/Makefile
--- linux-2.6.10/lib/Makefile~genetic-lib Fri Jan 28 15:49:40 2005
+++ linux-2.6.10-moilanen/lib/Makefile Fri Jan 28 15:49:40 2005
@@ -23,6 +23,7 @@ endif
obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
obj-$(CONFIG_CRC32) += crc32.o
obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
+obj-$(CONFIG_GENETIC_LIB) += genetic.o
obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff -puN /dev/null lib/genetic.c
--- /dev/null Fri Mar 14 06:52:15 2003
+++ linux-2.6.10-moilanen/lib/genetic.c Wed Feb 2 16:34:07 2005
@@ -0,0 +1,734 @@
+/*
+ * Genetic Algorithm Library
+ *
+ * Jake Moilanen <[EMAIL PROTECTED]>
+ * Copyright (C) 2004 IBM
+ *
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+/*
+ * Life cycle
+ *
+ * 1.) Create random children
+ * 2.) Run tests
+ * 3.) Calculate fitness
+ * 4.) Take top preformers
+ * 5.) Make children
+ * 6.) Mutate
+ * 7.) Goto step 2
+ */
+
+#include <linux/genetic.h>
+#include <linux/timer.h>
+#include <linux/jiffies.h>
+#include <linux/proc_fs.h>
+#include <linux/init.h>
+#include <linux/random.h>
+
+#include <asm/uaccess.h>
+#include <asm/string.h>
+#include <asm/bug.h>
+
+char genetic_lib_version[] = "0.2";
+
+int mutation_rate_change = GENETIC_DEFAULT_MUTATION_RATE_CHANGE;
+int genetic_lib_enabled = 1;
+
+static void genetic_ns_top_parents(phenotype_t *);
+static void genetic_ns_award_top_parents(phenotype_t *);
+static int genetic_create_children(phenotype_t *);
+static void genetic_split_performers(phenotype_t *);
+static void genetic_mutate(phenotype_t *);
+static void genetic_run_child(genetic_t * genetic);
+static void genetic_new_generation(genetic_t * genetic);
+
+void genetic_switch_child(unsigned long data);
+struct proc_dir_entry * genetic_root_dir = 0;
+
+extern int genetic_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data);
+extern int genetic_phenotype_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data);
+
+#if GENETIC_DEBUG
+extern int genetic_debug_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data);
+#endif
+
+
+int __init genetic_init(genetic_t ** in_genetic, unsigned long num_children,
+ unsigned long child_life_time,
+ char * name)
+{
+ struct proc_dir_entry *entry;
+ genetic_t * genetic;
+
+ if (!genetic_lib_enabled)
+ return 0;
+
+ printk(KERN_INFO "Initializing Genetic Library - version %s\n",
genetic_lib_version);
+
+ genetic = (genetic_t *)kmalloc(sizeof(genetic_t), GFP_KERNEL);
+ if (!genetic) {
+ printk(KERN_ERR "genetic_init: not enough memory\n");
+ return -ENOMEM;
+ }
+
+ *in_genetic = genetic;
+
+ genetic->name = (char *)kmalloc(strlen(name), GFP_KERNEL);
+ if (!genetic->name) {
+ printk(KERN_ERR "genetic_init: not enough memory\n");
+ kfree(genetic);
+ return -ENOMEM;
+ }
+
+ /* Init some of our values */
+ strcpy(genetic->name, name);
+
+ genetic->num_children = num_children;
+ genetic->child_life_time = child_life_time;
+
+ genetic->generation_number = 1;
+ genetic->child_number = 0;
+
+ /* Setup how long each child has to live */
+ init_timer(&genetic->timer);
+ genetic->timer.function = genetic_switch_child;
+ genetic->timer.data = (unsigned long)genetic;
+
+#ifdef CONFIG_PROC_FS
+ /* Setup proc structure to monitor */
+ if (!genetic_root_dir)
+ genetic_root_dir = proc_mkdir("genetic", 0);
+
+ genetic->dir = proc_mkdir(name, genetic_root_dir);
+
+ entry = create_proc_entry("stats", 0644, genetic->dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = genetic;
+ entry->read_proc = genetic_read_proc;
+ }
+
+#ifdef GENETIC_DEBUG
+ genetic->debug_dir = proc_mkdir("debug", genetic->dir);
+#endif /* GENETIC_DEBUG */
+
+
+#endif /* CONFIG_PROC_FS */
+
+ INIT_LIST_HEAD(&genetic->phenotype);
+
+ return 0;
+}
+
+int __init genetic_register_phenotype(genetic_t * genetic, struct genetic_ops
* ops,
+ unsigned long num_children, char * name,
+ unsigned long num_genes, unsigned long
uid)
+{
+ struct proc_dir_entry *entry;
+ phenotype_t * pt;
+ int rc;
+
+ if (!genetic_lib_enabled)
+ return 0;
+
+ printk(KERN_INFO "Initializing %s's phenotype %s\n", genetic->name,
name);
+
+ pt = (phenotype_t *)kmalloc(sizeof(phenotype_t), GFP_KERNEL);
+ if (!genetic) {
+ printk(KERN_ERR "genetic_register_phenotype: not enough
memory\n");
+ return -ENOMEM;
+ }
+
+ pt->name = (char *)kmalloc(strlen(name), GFP_KERNEL);
+ if (!pt->name) {
+ printk(KERN_ERR "genetic_register_phenotype: not enough
memory\n");
+ kfree(pt);
+ return -ENOMEM;
+ }
+
+ pt->child_ranking = (genetic_child_t **)kmalloc(num_children *
sizeof(genetic_child_t *), GFP_KERNEL);
+ if (!pt->child_ranking) {
+ printk(KERN_ERR "genetic_register_phenotype: not enough
memory\n");
+ kfree(pt->name);
+ kfree(pt);
+ return -ENOMEM;
+ }
+
+ strcpy(pt->name, name);
+
+ INIT_LIST_HEAD(&pt->children_queue[0]);
+ INIT_LIST_HEAD(&pt->children_queue[1]);
+
+ pt->run_queue = &pt->children_queue[0];
+ pt->finished_queue = &pt->children_queue[1];
+
+ pt->ops = ops;
+ pt->num_children = num_children;
+
+ pt->mutation_rate = GENETIC_DEFAULT_MUTATION_RATE;
+ pt->natural_selection = genetic_ns_top_parents;
+ pt->natural_selection_cutoff = num_children / 2;
+ pt->avg_fitness = 0;
+ pt->last_gen_avg_fitness = 0;
+ pt->child_number = 0;
+
+ pt->genetic = genetic;
+ pt->uid = uid;
+ pt->num_genes = num_genes;
+
+ /* Create some children */
+ rc = genetic_create_children(pt);
+ if (rc)
+ return rc;
+
+#ifdef CONFIG_PROC_FS
+ entry = create_proc_entry(name, 0644, genetic->dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = pt;
+ entry->read_proc = genetic_phenotype_read_proc;
+ }
+
+#endif
+
+#if GENETIC_DEBUG
+ pt->debug_index = 0;
+ /* create array for history. The +2 on num_genes is for the
+ fitness and child id */
+ pt->debug_size = num_children * (num_genes + 2) *
GENETIC_NUM_DEBUG_POINTS;
+
+ pt->debug_history = (long long *) kmalloc(pt->debug_size * sizeof(long
long), GFP_KERNEL);
+
+#ifdef CONFIG_PROC_FS
+ entry = create_proc_entry(name, 0644, genetic->debug_dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = pt;
+ entry->read_proc = genetic_debug_read_proc;
+ }
+
+#endif /* CONFIG_PROC_FS */
+#endif /* GENETIC_DEBUG */
+
+
+ list_add_tail(&pt->phenotype, &genetic->phenotype);
+
+ return 0;
+}
+
+void __init genetic_start(genetic_t * genetic)
+{
+ if (!genetic_lib_enabled)
+ return;
+
+ genetic_run_child(genetic);
+ printk(KERN_INFO "%ld children started in %s genetic library\n",
genetic->num_children, genetic->name);
+}
+
+
+
+/* create some children, it is up to the lib user to come up w/ a good
+ distro of genes for it's children */
+static int genetic_create_children(phenotype_t * pt)
+{
+ unsigned long i;
+ genetic_child_t * child;
+
+ for (i = 0; i < pt->num_children; i++) {
+ pt->child_ranking[i] = (genetic_child_t
*)kmalloc(sizeof(genetic_child_t), GFP_KERNEL);
+ if (!pt->child_ranking[i]) {
+ printk(KERN_ERR "genetic_create_child: not enough
memory\n");
+ for (i = i - 1; i >= 0; i--)
+ kfree(pt->child_ranking[i]);
+
+ return -ENOMEM;
+ }
+
+ child = pt->child_ranking[i];
+
+ child->id = i;
+
+ pt->ops->create_child(child);
+
+ list_add_tail(&child->list, pt->run_queue);
+ }
+
+ return 0;
+}
+
+/* See how well child did and run the next one */
+void genetic_switch_child(unsigned long data)
+{
+ genetic_t * genetic = (genetic_t *)data;
+ genetic_child_t * child;
+
+ struct list_head * p;
+ phenotype_t * pt;
+
+ int new_generation = 0;
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ child = list_entry(pt->run_queue->next, genetic_child_t, list);
+
+ list_del(&child->list);
+
+ list_add_tail(&child->list, pt->finished_queue);
+
+ if (pt->ops->calc_fitness)
+ pt->ops->calc_fitness(child);
+
+ pt->child_ranking[pt->child_number++] = child;
+
+ /* See if need more children */
+ if (list_empty(pt->run_queue))
+ new_generation = 1;
+ }
+
+ genetic->child_number++;
+
+ if (new_generation)
+ genetic_new_generation(genetic);
+
+ genetic_run_child(genetic);
+
+}
+
+/* Set the childs genes for run */
+void genetic_run_child(genetic_t * genetic)
+{
+ struct list_head * p;
+ phenotype_t * pt;
+
+ genetic_child_t * child;
+ void * genes;
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ child = list_entry(pt->run_queue->next, genetic_child_t, list);
+
+ genes = child->genes;
+
+ if (pt->ops->set_child_genes)
+ pt->ops->set_child_genes(genes);
+
+ if (pt->ops->take_snapshot)
+ pt->ops->take_snapshot(pt);
+ }
+
+ /* set a timer interrupt */
+ genetic->timer.expires = jiffies + genetic->child_life_time;
+ add_timer(&genetic->timer);
+
+}
+
+/* This natural selection routine will take the top
+ * natural_select_cutoff and use them to make children for the next
+ * generation and keep the top half perfomers
+ *
+ * This assumes natural_select_cutoff is exactly half of num_children
+ * and num_children is a multable of 4.
+ */
+static void genetic_ns_top_parents(phenotype_t * pt)
+{
+ unsigned long i,j,k = 0;
+ unsigned long num_children = pt->num_children;
+ unsigned long cutoff = num_children - pt->natural_selection_cutoff;
+
+ for (i = cutoff, j = num_children - 1; i < j; i++, j--, k += 2) {
+ /* create child A */
+ pt->ops->combine_genes(pt->child_ranking[i],
+ pt->child_ranking[j],
+ pt->child_ranking[k]);
+
+ /* create child B */
+ pt->ops->combine_genes(pt->child_ranking[i],
+ pt->child_ranking[j],
+ pt->child_ranking[k+1]);
+ }
+}
+
+/* This natural selection routine just has top parents populating
+ bottom performers. */
+static void genetic_ns_award_top_parents(phenotype_t * pt)
+{
+ unsigned long i;
+ unsigned long num_children = pt->num_children;
+ unsigned long cutoff = num_children - pt->natural_selection_cutoff;
+
+ for (i = 0; i < cutoff; i += 2) {
+ pt->ops->combine_genes(pt->child_ranking[num_children - 1],
+ pt->child_ranking[num_children - 2],
+ pt->child_ranking[i]);
+
+ pt->ops->combine_genes(pt->child_ranking[num_children - 1],
+ pt->child_ranking[num_children - 2],
+ pt->child_ranking[i+1]);
+ }
+}
+
+static inline void genetic_swap(genetic_child_t ** a, genetic_child_t ** b)
+{
+ genetic_child_t * tmp = *a;
+
+ *a = *b;
+ *b = tmp;
+}
+
+/* bubble sort */
+/* XXX change this to quick sort */
+static void genetic_split_performers(phenotype_t * pt)
+{
+ int i, j;
+
+ for (i = pt->num_children; i > 1; i--)
+ for (j = 0; j < i - 1; j++)
+ if (pt->child_ranking[j]->fitness >
pt->child_ranking[j+1]->fitness)
+ genetic_swap(&pt->child_ranking[j], &pt->child_ranking[j+1]);
+}
+
+static void genetic_mutate(phenotype_t * pt)
+{
+ long child_entry = -1;
+ int i;
+
+ if (!pt->num_genes)
+ return;
+
+ for (i = 0; i < pt->num_mutations; i++) {
+ get_random_bytes(&child_entry, sizeof(child_entry));
+ child_entry = child_entry % pt->num_children;
+
+ pt->ops->mutate_child(pt->child_ranking[child_entry]);
+ }
+}
+
+/* XXX This will either aid in handling new workloads, or send us on a
+ downward spiral */
+static void genetic_shift_mutation_rate(phenotype_t * pt, long long
prev_gen_avg_fitness, long long avg_fitness)
+{
+ if (mutation_rate_change && pt->genetic->generation_number > 1) {
+
+ if (pt->ops->shift_mutation_rate) {
+ pt->ops->shift_mutation_rate(pt);
+ } else {
+
+ if (avg_fitness > prev_gen_avg_fitness)
+ pt->mutation_rate -= mutation_rate_change;
+ else if (avg_fitness < prev_gen_avg_fitness)
+ pt->mutation_rate += mutation_rate_change;
+
+ if (pt->mutation_rate > GENETIC_MAX_MUTATION_RATE)
+ pt->mutation_rate = GENETIC_MAX_MUTATION_RATE;
+ else if (pt->mutation_rate < GENETIC_MIN_MUTATION_RATE)
+ pt->mutation_rate = GENETIC_MIN_MUTATION_RATE;
+ }
+ }
+}
+
+void genetic_general_shift_mutation_rate(phenotype_t * in_pt)
+{
+ struct list_head * p;
+ phenotype_t * pt;
+ int count = 0;
+ long rate = 0;
+
+ list_for_each(p, &in_pt->genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ if (in_pt->uid & pt->uid && in_pt->uid != pt->uid) {
+ rate += pt->mutation_rate;
+ count++;
+ }
+ }
+
+ /* If we are a general phenotype that is made up of other
+ phenotypes then we take the average */
+ if (count)
+ in_pt->mutation_rate = (rate / count);
+ else
+ in_pt->mutation_rate = mutation_rate_change;
+}
+
+static void genetic_calc_stats(phenotype_t * pt)
+{
+ long long total_fitness = 0;
+ long long prev_gen_avg_fitness = pt->last_gen_avg_fitness;
+ long long tmp_fitness;
+ long dummy;
+ int i;
+
+ /* calculate the avg fitness for this generation and avg fitness
+ * so far */
+ for (i = 0; i < pt->num_children; i++)
+ total_fitness += pt->child_ranking[i]->fitness;
+
+ pt->last_gen_avg_fitness = total_fitness >> long_log2(pt->num_children);
+
+ /* Mutation rate calibration */
+ genetic_shift_mutation_rate(pt, prev_gen_avg_fitness,
pt->last_gen_avg_fitness);
+
+ pt->num_mutations = ((pt->num_children * pt->num_genes) *
pt->mutation_rate) / 100;
+
+ /* calc new avg fitness */
+ tmp_fitness = pt->last_gen_avg_fitness - pt->avg_fitness;
+ divll(&tmp_fitness, pt->genetic->generation_number, &dummy);
+ pt->avg_fitness += tmp_fitness;
+
+ pt->fitness_history[pt->fitness_history_index++ & GENETIC_HISTORY_MASK]
=
+ pt->last_gen_avg_fitness;
+
+}
+
+#if GENETIC_DEBUG
+/* Stores attributes into an array in the following format
+ * child_num fitness gene[0] gene[1] .... gene[num_genes-1]
+ * Add +1 to GENETIC_NUM_DEBUG_POINTS if add another dump_children
+ * call
+ */
+void dump_children(phenotype_t * pt)
+{
+ int i, j;
+ long * genes;
+ unsigned long debug_size = pt->debug_size;
+
+ for (i = 0; i < pt->num_children; i++) {
+ pt->debug_history[pt->debug_index++ % debug_size] =
pt->child_ranking[i]->id;
+ pt->debug_history[pt->debug_index++ % debug_size] =
pt->child_ranking[i]->fitness;
+
+ genes = (long *)pt->child_ranking[i]->genes;
+
+ for (j = 0; j < pt->child_ranking[i]->num_genes; j++) {
+ pt->debug_history[pt->debug_index++ % debug_size] =
genes[j];
+ }
+ }
+}
+#else
+void dump_children(genetic_t * genetic) { return; }
+#endif
+
+void genetic_new_generation(genetic_t * genetic)
+{
+ struct list_head * tmp;
+
+ struct list_head * p;
+ phenotype_t * pt;
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ /* Check to see if need to recalibrate fitness to take
+ other phenotypes' rankings into account. This
+ should be ran after all phenotypes that have input
+ have been ran. */
+ if (pt->ops->calc_post_fitness)
+ pt->ops->calc_post_fitness(pt);
+
+ dump_children(pt);
+
+ /* figure out top performers */
+ genetic_split_performers(pt);
+
+ /* calc stats */
+ genetic_calc_stats(pt);
+
+ dump_children(pt);
+
+ /* make some new children */
+ if (pt->num_genes)
+ pt->natural_selection(pt);
+
+ dump_children(pt);
+
+ /* mutate a couple of the next generation */
+ genetic_mutate(pt);
+
+ dump_children(pt);
+
+ /* Move the new children still sitting in the finished queue to
+ the run queue */
+ tmp = pt->run_queue;
+ pt->run_queue = pt->finished_queue;
+ pt->finished_queue = tmp;
+
+ pt->child_number = 0;
+ pt->debug_index = 0;
+
+ }
+
+ genetic->child_number = 0;
+ genetic->generation_number++;
+
+}
+
+/* Mutate a gene picking a random value within the gene range */
+void genetic_generic_random_mutate_gene(genetic_child_t * child, long gene_num)
+{
+ unsigned long *genes = (unsigned long *)child->genes;
+ unsigned long min = child->gene_param[gene_num].min;
+ unsigned long max = child->gene_param[gene_num].max;
+ unsigned long gene_value;
+ unsigned long range = max - min + 1;
+
+ /* create a mutation value */
+ get_random_bytes(&gene_value, sizeof(gene_value));
+
+ gene_value = gene_value % range;
+
+ genes[gene_num] = min + gene_value;
+}
+
+void genetic_generic_iterative_mutate_gene(genetic_child_t * child, long
gene_num)
+{
+ unsigned long *genes = (unsigned long *)child->genes;
+ long min = child->gene_param[gene_num].min;
+ long max = child->gene_param[gene_num].max;
+ long change;
+ long old_value = genes[gene_num];
+ long new_value;
+ unsigned long range = max - min + 1;
+
+ /* If under 5, random might work better */
+ if (range < 5)
+ return genetic_generic_random_mutate_gene(child, gene_num);
+
+ /* get the % of change */
+ get_random_bytes(&change, sizeof(change));
+
+ change = change % GENETIC_ITERATIVE_MUTATION_RANGE;
+
+
+ new_value = ((long)(change * range) / (long)100) + old_value;
+
+ if (new_value > max)
+ new_value = max;
+ else if (new_value < min)
+ new_value = min;
+
+ genes[gene_num] = new_value;
+}
+
+/* This assumes that all genes are a unsigned long array of size
+ num_genes */
+void genetic_generic_mutate_child(genetic_child_t * child)
+{
+ long gene_num = -1;
+
+ /* pick a random gene */
+ get_random_bytes(&gene_num, sizeof(gene_num));
+
+ if (gene_num < 0)
+ gene_num = -gene_num;
+
+ gene_num = gene_num % child->num_genes;
+
+ if (child->gene_param[gene_num].mutate_gene)
+ child->gene_param[gene_num].mutate_gene(child, gene_num);
+ else
+ genetic_generic_random_mutate_gene(child, gene_num);
+}
+
+void genetic_create_child_defaults(genetic_child_t * child)
+{
+ int i;
+ unsigned long * genes = child->genes;
+
+ for (i = 0; i < child->num_genes; i++) {
+ genes[i] = child->gene_param[i].initial;
+ }
+}
+
+void genetic_create_child_spread(genetic_child_t * child, unsigned long
num_children)
+{
+ int i;
+ unsigned long range;
+ int range_incr;
+ int child_num = child->id;
+ long num_genes = child->num_genes;
+ unsigned long * genes = child->genes;
+
+ for (i = 0; i < num_genes; i++) {
+ range = child->gene_param[i].max - child->gene_param[i].min + 1;
+ range_incr = range / num_children;
+ if (range_incr)
+ genes[i] = child->gene_param[i].min +
+ (range_incr * child_num);
+ else
+ genes[i] = child->gene_param[i].min +
+ (child_num / (num_children / range));
+ }
+
+}
+
+/* Randomly pick which parent to use for each gene to create a child */
+void genetic_generic_combine_genes(genetic_child_t * parent_a,
+ genetic_child_t * parent_b,
+ genetic_child_t * child)
+{
+ unsigned long * genes_a = (unsigned long *)parent_a->genes;
+ unsigned long * genes_b = (unsigned long *)parent_b->genes;
+ unsigned long * child_genes = (unsigned long *)child->genes;
+
+ /* Assume parent_a and parent_b have same num_genes */
+ unsigned long num_genes = parent_a->num_genes;
+ int parent_selector;
+ int i, j;
+
+ for (i = 0; i < num_genes; i++) {
+ get_random_bytes(&parent_selector, sizeof(parent_selector));
+
+ /* Look at each bit to determine which parent to use */
+ for (j = 0; j < (sizeof(parent_selector) * 8); j++) {
+ if (parent_selector & 1) {
+ child_genes[i] = genes_a[i];
+ } else {
+ child_genes[i] = genes_b[i];
+ }
+ parent_selector >>= 1;
+ }
+ }
+}
+
+static int __init genetic_boot_setup(char *str)
+{
+ if (strcmp(str, "on") == 0)
+ genetic_lib_enabled = 1;
+ else if (strcmp(str, "off") == 0)
+ genetic_lib_enabled = 0;
+
+ return 1;
+}
+
+
+static int __init genetic_mutation_rate_change_setup(char *str)
+{
+ int i;
+
+ if (get_option(&str,&i)) {
+
+ if (i > GENETIC_MAX_MUTATION_RATE)
+ i = GENETIC_MAX_MUTATION_RATE;
+ else if (i < 0)
+ i = 0;
+
+ mutation_rate_change = i;
+ }
+
+ return 1;
+
+}
+__setup("genetic=", genetic_boot_setup);
+__setup("genetic_mutate_rate=", genetic_mutation_rate_change_setup);
_
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
