lkml.org 
[lkml]   [2005]   [Jan]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[ANNOUNCE 1/4][RFC] Genetic Algorithm Library
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 <moilanen@austin.ibm.com>

---


diff -puN fs/proc/proc_misc.c~genetic-lib fs/proc/proc_misc.c
--- linux-2.6.9/fs/proc/proc_misc.c~genetic-lib Wed Jan 5 15:45:54 2005
+++ linux-2.6.9-moilanen/fs/proc/proc_misc.c Wed Jan 5 15:45:54 2005
@@ -45,6 +45,7 @@
#include <linux/sysrq.h>
#include <linux/vmalloc.h>
#include <linux/sched_cpustats.h>
+#include <linux/genetic.h>
#include <asm/uaccess.h>
#include <asm/pgtable.h>
#include <asm/io.h>
@@ -233,6 +234,35 @@ 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 i;
+ int n = 0;
+ genetic_t * genetic = (genetic_t *)data;
+
+ n = sprintf(page, "generation_number:\t%ld\n", genetic->generation_number);
+ n += sprintf(page+n, "num_children:\t\t%ld\n", genetic->num_children);
+ n += sprintf(page+n, "child_number:\t\t%ld\n", genetic->child_number);
+ n += sprintf(page+n, "num_mutations:\t\t%ld\n", genetic->num_mutations);
+ n += sprintf(page+n, "avg_fitness:\t\t%ld\n", genetic->avg_fitness);
+ n += sprintf(page+n, "last_gen_avg_fitness:\t%ld\n", genetic->last_gen_avg_fitness);
+
+ n += sprintf(page+n, "\nFitness history\n");
+
+ for (i = genetic->generation_number > GENETIC_HISTORY_SIZE ? GENETIC_HISTORY_SIZE
+ : genetic->generation_number-1; i > 0; i--)
+ n += sprintf(page+n, "generation(%ld):\t%ld\n",
+ genetic->generation_number - i,
+ genetic->fitness_history[(genetic->fitness_history_index - i) & GENETIC_HISTORY_MASK]);
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+#endif

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.9-moilanen/include/linux/genetic.h Wed Jan 5 15:45:54 2005
@@ -0,0 +1,103 @@
+#ifndef __LINUX_GENETIC_H
+#define __LINUX_GENETIC_H
+/*
+ * include/linux/genetic.h
+ *
+ * Jake Moilanen <moilanen@austin.ibm.com>
+ * 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_DEFAULT_NUM_MUTATIONS 8
+#define GENETIC_HISTORY_SIZE 0x10
+#define GENETIC_HISTORY_MASK (GENETIC_HISTORY_SIZE - 1)
+
+#define GENETIC_DEBUG 0
+
+#define gen_dbg(format, arg...) do { if (GENETIC_DEBUG) printk(KERN_EMERG __FILE__ ": " format "\n" , ## arg); } while (0)
+#define gen_trc(format, arg...) do { if (GENETIC_DEBUG) printk(KERN_EMERG __FILE__ ":%s:%d\n" , __FUNCTION__, __LINE__); } while (0)
+
+struct gene_param_s;
+
+struct genetic_child_s {
+ struct list_head child;
+ long fitness;
+ unsigned long num_genes;
+ void *genes;
+ struct gene_param_s *gene_param;
+ void *stats_snapshot;
+};
+
+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 genetic_s {
+ struct list_head children_queue[2];
+ struct list_head *run_queue;
+ struct list_head *finished_queue;
+ unsigned long child_life_time;
+ unsigned long num_children; /* Must be power of 2 */
+ unsigned long natural_selection_cutoff; /* How many children
+ * will survive
+ */
+ unsigned long num_mutations;
+
+ void (*natural_selection)(struct genetic_s *);
+
+ char *name;
+ struct timer_list timer;
+ struct genetic_ops *ops;
+
+ genetic_child_t **child_ranking;
+
+ /* performance metrics */
+ long avg_fitness;
+ long last_gen_avg_fitness;
+
+ unsigned long generation_number;
+ unsigned long child_number;
+
+ unsigned long fitness_history_index;
+ long fitness_history[GENETIC_HISTORY_SIZE];
+
+};
+
+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 *, genetic_child_t *);
+ void (*mutate_child)(genetic_child_t *);
+};
+
+extern int __init genetic_init(genetic_t * genetic, struct genetic_ops * ops, unsigned long num_children, unsigned long child_life_time, char * name);
+extern void genetic_generic_mutate_child(genetic_child_t * child);
+extern void genetic_generic_combine_genes(genetic_child_t * parent_a,
+ genetic_child_t * parent_b,
+ genetic_child_t * child_a,
+ genetic_child_t * child_b);
+
+
+#endif
diff -puN lib/Kconfig~genetic-lib lib/Kconfig
--- linux-2.6.9/lib/Kconfig~genetic-lib Wed Jan 5 15:45:54 2005
+++ linux-2.6.9-moilanen/lib/Kconfig Wed Jan 5 15:45:54 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.9/lib/Makefile~genetic-lib Wed Jan 5 15:45:54 2005
+++ linux-2.6.9-moilanen/lib/Makefile Wed Jan 5 15:45:54 2005
@@ -18,6 +18,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.9-moilanen/lib/genetic.c Wed Jan 5 15:45:54 2005
@@ -0,0 +1,429 @@
+/*
+ * Genetic Algorithm Library
+ *
+ * Jake Moilanen <moilanen@austin.ibm.com>
+ * 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>
+
+static void genetic_ns_top_parents(genetic_t * genetic);
+static void genetic_ns_award_top_parents(genetic_t * genetic);
+static void genetic_create_children(genetic_t * genetic);
+static void genetic_split_performers(genetic_t * genetic);
+static void genetic_mutate(genetic_t * genetic);
+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);
+
+int __init genetic_init(genetic_t * genetic, struct genetic_ops * ops,
+ unsigned long num_children, unsigned long child_life_time,
+ char * name)
+{
+ struct proc_dir_entry *entry;
+
+ genetic = (genetic_t *)kmalloc(sizeof(genetic_t), GFP_KERNEL);
+ if (!genetic) {
+ printk(KERN_ERR "genetic_init: not enough memory\n");
+ return -ENOMEM;
+ }
+
+ genetic->name = (char *)kmalloc(strlen(name), GFP_KERNEL);
+ if (!genetic->name) {
+ kfree(genetic);
+ return -ENOMEM;
+ }
+
+ genetic->child_ranking = (genetic_child_t **)kmalloc(num_children * sizeof(genetic_child_t *), GFP_KERNEL);
+ if (!genetic->child_ranking) {
+ kfree(genetic->name);
+ kfree(genetic);
+ return -ENOMEM;
+ }
+
+ /* Init some of our values */
+ strcpy(genetic->name, name);
+
+ INIT_LIST_HEAD(&genetic->children_queue[0]);
+ INIT_LIST_HEAD(&genetic->children_queue[1]);
+
+ genetic->run_queue = &genetic->children_queue[0];
+ genetic->finished_queue = &genetic->children_queue[1];
+
+ genetic->ops = ops;
+ genetic->num_children = num_children;
+ genetic->child_life_time = child_life_time;
+
+ genetic->generation_number = 1;
+ genetic->child_number = 0;
+ genetic->num_mutations = GENETIC_DEFAULT_NUM_MUTATIONS;
+ genetic->natural_selection = genetic_ns_top_parents;
+ genetic->natural_selection_cutoff = num_children / 2;
+ genetic->avg_fitness = 0;
+ genetic->last_gen_avg_fitness = 0;
+
+ /* Create some children */
+ genetic_create_children(genetic);
+
+ /* 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);
+
+ entry = create_proc_entry(name, 0644, genetic_root_dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = genetic;
+ entry->read_proc = genetic_read_proc;
+ }
+#endif
+
+ genetic_run_child(genetic);
+
+ printk(KERN_INFO "%ld children started in %s genetic library\n", num_children, name);
+
+ return 0;
+}
+
+/* create some children, it is up to the lib user to come up w/ a good
+ distro of genes for it's children */
+static void genetic_create_children(genetic_t * genetic)
+{
+ unsigned long i;
+ genetic_child_t * child;
+
+ for (i = 0; i < genetic->num_children; i++) {
+ genetic->child_ranking[i] = (genetic_child_t *)kmalloc(sizeof(genetic_child_t), GFP_KERNEL);
+ child = genetic->child_ranking[i];
+
+ genetic->ops->create_child(child);
+
+ list_add_tail(&child->child, genetic->run_queue->next);
+ }
+}
+
+/* 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;
+
+ child = list_entry(genetic->run_queue->next, genetic_child_t, child);
+
+ list_del(&child->child);
+
+ list_add_tail(&child->child, genetic->finished_queue->next);
+
+ genetic->ops->calc_fitness(child);
+
+ genetic->child_ranking[genetic->child_number++] = child;
+
+ /* See if need more children */
+ if (list_empty(genetic->run_queue->next))
+ genetic_new_generation(genetic);
+
+ genetic_run_child(genetic);
+}
+
+/* Set the childs genes for run */
+void genetic_run_child(genetic_t * genetic)
+{
+ genetic_child_t * child = list_entry(genetic->run_queue->next, genetic_child_t, child);
+ void * genes = child->genes;
+
+ BUG_ON(!genes);
+
+ genetic->ops->set_child_genes(genes);
+
+ /* 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(genetic_t * genetic)
+{
+ unsigned long i,j,k = 0;
+ unsigned long num_children = genetic->num_children;
+ unsigned long cutoff = num_children - genetic->natural_selection_cutoff;
+
+ for (i = cutoff, j = num_children - 1; i < j; i++, j--, k += 2) {
+ genetic->ops->combine_genes(genetic->child_ranking[i],
+ genetic->child_ranking[j],
+ genetic->child_ranking[k],
+ genetic->child_ranking[k+1]);
+ }
+}
+
+static void genetic_ns_clone_top_parents(genetic_t * genetic)
+{
+ unsigned long i,j,k = 0;
+ unsigned long num_children = genetic->num_children;
+ unsigned long cutoff = num_children - genetic->natural_selection_cutoff;
+
+ for (i = cutoff, j = num_children - 1; i < j; i++, j--, k += 2) {
+ genetic->ops->combine_genes(genetic->child_ranking[i],
+ genetic->child_ranking[j],
+ genetic->child_ranking[k],
+ genetic->child_ranking[k+1]);
+ }
+}
+
+/* This natural selection routine just has top parents populating
+ bottom performers. */
+static void genetic_ns_award_top_parents(genetic_t * genetic)
+{
+ unsigned long i;
+ unsigned long num_children = genetic->num_children;
+ unsigned long cutoff = num_children - genetic->natural_selection_cutoff;
+
+ for (i = 0; i < cutoff; i += 2) {
+ genetic->ops->combine_genes(genetic->child_ranking[num_children - 1],
+ genetic->child_ranking[num_children - 2],
+ genetic->child_ranking[i],
+ genetic->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(genetic_t * genetic)
+{
+ int i, j;
+
+ for (i = genetic->num_children; i > 1; i--)
+ for (j = 0; j < i - 1; j++)
+ if (genetic->child_ranking[j]->fitness > genetic->child_ranking[j+1]->fitness)
+ genetic_swap(&genetic->child_ranking[j], &genetic->child_ranking[j+1]);
+}
+
+static void genetic_mutate(genetic_t * genetic)
+{
+ long child_entry = -1;
+ int i;
+
+ for (i = 0; i < genetic->num_mutations; i++) {
+ get_random_bytes(&child_entry, sizeof(child_entry));
+ child_entry = child_entry % genetic->num_children;
+
+ genetic->ops->mutate_child(genetic->child_ranking[child_entry]);
+ }
+}
+
+static void genetic_calc_stats(genetic_t * genetic)
+{
+ long total_fitness = 0;
+ int i;
+
+ /* calculate the avg fitness for this generation and avg fitness
+ * so far */
+ for (i = 0; i < genetic->num_children; i++)
+ total_fitness += genetic->child_ranking[i]->fitness;
+
+ genetic->last_gen_avg_fitness = total_fitness / (long)genetic->num_children;
+
+ genetic->avg_fitness = ((genetic->avg_fitness * (long)(genetic->generation_number - 1)) +
+ genetic->last_gen_avg_fitness) / (long)genetic->generation_number;
+
+ genetic->fitness_history[genetic->fitness_history_index++ & GENETIC_HISTORY_MASK] =
+ genetic->last_gen_avg_fitness;
+
+}
+
+void dump_children(genetic_t * genetic)
+{
+ int i, j;
+ long * genes;
+ for (i = 0; i < genetic->num_children; i++) {
+ printk(KERN_EMERG "%d: %-8ld:\t", i, genetic->child_ranking[i]->fitness);
+
+ for (j = 0; j < genetic->child_ranking[i]->num_genes; j++) {
+ genes = (long *)genetic->child_ranking[i]->genes;
+ printk("%ld\t", genes[j]);
+ }
+ printk("\n");
+ }
+
+ printk("\n");
+}
+
+void genetic_new_generation(genetic_t * genetic)
+{
+ struct list_head * tmp;
+
+#if GENETIC_DEBUG
+ printk(KERN_EMERG "-------------------------\n");
+ printk(KERN_EMERG "new generation performers: \n");
+ dump_children(genetic);
+#endif
+
+ /* figure out top performers */
+ genetic_split_performers(genetic);
+
+#if GENETIC_DEBUG
+ printk(KERN_EMERG "split performers: \n");
+ dump_children(genetic);
+#endif
+
+ /* calc stats */
+ genetic_calc_stats(genetic);
+
+ /* make some new children */
+ genetic->natural_selection(genetic);
+
+#if GENETIC_DEBUG
+ printk(KERN_EMERG "selected: \n");
+ dump_children(genetic);
+#endif
+
+ /* mutate a couple of the next generation */
+ genetic_mutate(genetic);
+
+#if GENETIC_DEBUG
+ printk(KERN_EMERG "mutated: \n");
+ dump_children(genetic);
+#endif
+
+ /* Move the new children still sitting in the finished queue to
+ the run queue */
+ tmp = genetic->run_queue;
+ genetic->run_queue = genetic->finished_queue;
+ genetic->finished_queue = tmp;
+
+ genetic->child_number = 0;
+ genetic->generation_number++;
+
+}
+
+void genetic_generic_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));
+
+#if 0
+ /* XXX we shouldn't need this now that it's unsigned */
+ if (gene_value < 0)
+ gene_value = -gene_value;
+#endif
+
+ gene_value = gene_value % range;
+
+ genes[gene_num] = min + gene_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_mutate_gene(child, gene_num);
+}
+
+
+/* combine the genes by randomly take a portion of A's and B's to make
+ * C. Then flip that portion of B and A to make D */
+void genetic_generic_combine_genes(genetic_child_t * parent_a,
+ genetic_child_t * parent_b,
+ genetic_child_t * child_a,
+ genetic_child_t * child_b)
+{
+ unsigned long * genes_a = (unsigned long *)parent_a->genes;
+ unsigned long * genes_b = (unsigned long *)parent_b->genes;
+ unsigned long * genes_c = (unsigned long *)child_a->genes;
+ unsigned long * genes_d = (unsigned long *)child_b->genes;
+ /* Assume parent_a and parent_b have same num_genes */
+ unsigned long num_genes = parent_a->num_genes;
+ int combine_point;
+ int i;
+
+ get_random_bytes(&combine_point, sizeof(combine_point));
+
+ if (combine_point < 0)
+ combine_point = -combine_point;
+
+ combine_point = combine_point % num_genes;
+
+ for (i = combine_point; i < num_genes; i++)
+ genes_c[i] = genes_a[i];
+
+ for (i = 0; i < combine_point; i++)
+ genes_c[i] = genes_b[i];
+
+ for (i = combine_point; i < num_genes; i++)
+ genes_d[i] = genes_b[i];
+
+ for (i = 0; i < combine_point; i++)
+ genes_d[i] = genes_a[i];
+}
_

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:09    [W:0.549 / U:0.032 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site