GSoC Evolutionary Algorithm Proposal

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

GSoC Evolutionary Algorithm Proposal

deneche abdelhakim
I've written my proposal, and because I could no more change it after I submit it to GSoc, I first post it here
if someone have some suggestions you are welcome.
I will wait until saturday morning to post it to the GSoC

**************************************************************************************
Application for Summer of Code 2008    Mahout Project

Deneche Abdel Hakim

Codename Mahout.GA


I. Synopsis

I will add a genetic algorithm (GA) for binary classification on large datasets to the Mahout project. To gain time I will use an existing framework for genetic algorithms WatchMaker [WatchMaker] with an Apache Software License. I will also add a parallelized measure that indicates the quality of classification rules on a given dataset, this measure will be available independently of the GA. And if I have enough time I will make the GA more generic and apply it on a different problem (multiclass classification).


II. Project

A GA works by evolving a population of individuals toward a desired goal. To get a satisfying solution, the GA needs to run thousands of iterations with hundreds of individuals. For each iteration and individual the fitness is calculated, it indicates the closeness of that individual to the desired solution. The main advantage of GAs is there ability to find solution of problems given only a fitness measure (and of course a sufficient CPU power), this is particularly helpful when the problem is complex and no mathematical solution is available.

My primary goal is to implement the GA described in [GA]. It uses a fitness function that is easy to implement and can benefit from the Map-Reduce strategy to exploit distributed computing (when the training dataset is very large). It will be available as ready to use tool (Mahout.GA) that discovers binary classification rules for any given dataset. Concretely, the main program will launch the GA using WatchMaker, each time the GA needs to evaluate the fitness of the population it calls a specific class given by us, this class will configure and launch a Hadoop Job on a distributed cluster.

My secondary goal is to make Mahout.GA problem independent, thus allowing us to use it for different problems such as multiclass classification, optimization, clustering. This will be done by implementing a ready to use generic fitness function for WatchMaker that calls internally Hadoop. As a proof of concept I will use it for multiclass classification (if I don't run out of time of course!).


III. Profit for Mahout

1.The GA will be integrated with Mahout as a ready to use rule discovering tool for binary classification;
2.Explore the integration of existing frameworks with Mahout, for example how to design the program in a way that the framework libraries will not be needed in the slave nodes (technically its feasible, but I still need to learn how to do it);
3.The parallelized fitness function can be used independently of Mahout.GA. It’s a good measure of the quality of binary classification rules;
4.Simplify the process of using Mahout.GA for other problems. The user will still need to design the solutions representation and to implement a fitness function, but all the Hadoop stuff should be hidden or at least made simpler;
5.Apply the generalized Mahout.GA to multiclass classification and write a corresponding tutorial that explains how to use Mahout.GA to solve new problems.


IV. Success Criteria

Main goals
  1.Implement the parallelized fitness function described in [GA] and validate its results on a small dataset;
  2.Implement Mahout.GA for binary classification rule discovery. A simpler (not parallelized) version of this algorithm should also be implemented to     validate the results of Mahout.GA;

Secondary goals
  1.Allow the parallelized fitness function to be used independently of Mahout.GA;
  2.Use Mahout.GA on a different problem (multiclass classification) and write a corresponding tutorial.


V. Roadmap

[April, 14: accepted students known]
  1.Familiarize myself with Hadoop
    Modify one of the examples of Hadoop to simulate an iterative process. For each iteration, a new Job is executed with different parameters, and its results are imported back by the program.
  2.Implement the GA without parallelism
    a.Start by implementing the tutorial example that comes with WatchMaker;
    b.Implement my own Individual and Fitness function classes;
    c.Validate the algorithm using a small dataset, and find the parameters that will give acceptable results.
  3.Prepare whatever I may need in the development period
[May, 26 coding starts]
  4.Implement the parallelized fitness function
    a.Use Hadoop Map-Reduce to implement it [2 weeks];
    b.Validate it on a small dataset [1 week].
  5.Implement Mahout.GA
    a.Write an intermediary component between WatchMaker and the parallelized fitness function. This component takes a population, configures and launches a Job, waits for its end, then returns the calculated fitness values [2 weeks];
    b.Validate Mahout.GA by comparing its results with the GA without parallelism [1 week].
[July, 7-14 mid term evaluation]
  6.Generic Mahout.GA
    a.Identify the components that are problem dependant, and make them less dependant of Hadoop as much as possible [2 weeks];
    b.Implement the components for the multiclass classification problem and validate Mahout.GA on a given dataset [2 week];
    c.Write a tutorial that explains how to use Mahout.GA to solve new problems (in this case the multiclass classification problem) [in parallel with 5.b].
[August, 11 suggested pencil 'down' date]
  Clean the code and arrange the documentation.
[August, 18 final evaluations]

Note that this plan may change given my interaction with my Mentor and the Mahout community.

VI. Biography

I am a PhD student at the University Mentouri of Constantine. My primary research goal is a framework to help build Intelligent Adaptive Systems. I am still on my first year, and there is a good chance that I will be working on Distributed Evolutionary Algorithms for the next three years.

For the purpose of my Master, I worked on Artificial Immune Systems. I applied them to handwritten digits recognition [PatternRecognition] and Muliple Sequence Alignement (bioinformatics) [BioInformatics]. I also built a feature selection operator for Yale (but for lack of time I never published it), and participated in an internship at the LIFL laboratory (Lille, France), where I implemented several operators for a C++ evolutionary computation framework [ParadisEO].

In parallel to my Master, I worked as a freelance programmer for my University. I developed a Java scholar management system using Eclipse, TortoiseSVN and many open source libraries. I gained a good experience on project management (how to make a realistic plan and stick to it) and open source development (how to choose a good open source library, use it, and work around known bugs).

VII. References
[GA]    Bojarczuk CC, Lopes HS, and Freitas AA. "Discovering comprehensible classification rules using genetic programming: a case study in a medical domain". Proc. Genetic and Evolutionary Computation Conference GECCO99, 953-958. Orlando, FL, USA, July 1999.

[WatchMaker]    https://watchmaker.dev.java.net/

[PatternRecognition]    S. Meshoul, A. Deneche, M. Batouche, "Combining an Artificial Immune System with a Clustering Method for Effective Pattern Recognition", International Conference on Machine Intelligence ICMI’05, pp. 782-787, Tunis 2005.

[BioInformatics]    A. Layeb, A. Deneche, "Multiple Sequence Alignment by Immune Artificial System", ACS/IEEE International Conference on Computer Systems and Applications AICCSA’07, Jordan 2007.

[ParadisEO]    http://paradiseo.gforge.inria.fr/index.php?n=Paradiseo.Home?from=Main.HomePage

----------------------------------------------------------------------------------------------
This proposal is inspired from the excellent one of Konstantin Kafer [http://drupal.org/files/application.pdf]
*********************************************************************************************************



      _____________________________________________________________________________
Envoyez avec Yahoo! Mail. Capacité de stockage illimitée pour vos emails. http://mail.yahoo.fr
Reply | Threaded
Open this post in threaded view
|

Re: GSoC Evolutionary Algorithm Proposal

Grant Ingersoll-2
+1

On Mar 27, 2008, at 9:18 AM, deneche abdelhakim wrote:

> I've written my proposal, and because I could no more change it  
> after I submit it to GSoc, I first post it here
> if someone have some suggestions you are welcome.
> I will wait until saturday morning to post it to the GSoC
>
> **************************************************************************************
> Application for Summer of Code 2008    Mahout Project
>
> Deneche Abdel Hakim
>
> Codename Mahout.GA
>
>
> I. Synopsis
>
> I will add a genetic algorithm (GA) for binary classification on  
> large datasets to the Mahout project. To gain time I will use an  
> existing framework for genetic algorithms WatchMaker [WatchMaker]  
> with an Apache Software License. I will also add a parallelized  
> measure that indicates the quality of classification rules on a  
> given dataset, this measure will be available independently of the  
> GA. And if I have enough time I will make the GA more generic and  
> apply it on a different problem (multiclass classification).
>
>
> II. Project
>
> A GA works by evolving a population of individuals toward a desired  
> goal. To get a satisfying solution, the GA needs to run thousands of  
> iterations with hundreds of individuals. For each iteration and  
> individual the fitness is calculated, it indicates the closeness of  
> that individual to the desired solution. The main advantage of GAs  
> is there ability to find solution of problems given only a fitness  
> measure (and of course a sufficient CPU power), this is particularly  
> helpful when the problem is complex and no mathematical solution is  
> available.
>
> My primary goal is to implement the GA described in [GA]. It uses a  
> fitness function that is easy to implement and can benefit from the  
> Map-Reduce strategy to exploit distributed computing (when the  
> training dataset is very large). It will be available as ready to  
> use tool (Mahout.GA) that discovers binary classification rules for  
> any given dataset. Concretely, the main program will launch the GA  
> using WatchMaker, each time the GA needs to evaluate the fitness of  
> the population it calls a specific class given by us, this class  
> will configure and launch a Hadoop Job on a distributed cluster.
>
> My secondary goal is to make Mahout.GA problem independent, thus  
> allowing us to use it for different problems such as multiclass  
> classification, optimization, clustering. This will be done by  
> implementing a ready to use generic fitness function for WatchMaker  
> that calls internally Hadoop. As a proof of concept I will use it  
> for multiclass classification (if I don't run out of time of course!).
>
>
> III. Profit for Mahout
>
> 1.The GA will be integrated with Mahout as a ready to use rule  
> discovering tool for binary classification;
> 2.Explore the integration of existing frameworks with Mahout, for  
> example how to design the program in a way that the framework  
> libraries will not be needed in the slave nodes (technically its  
> feasible, but I still need to learn how to do it);
> 3.The parallelized fitness function can be used independently of  
> Mahout.GA. It’s a good measure of the quality of binary  
> classification rules;
> 4.Simplify the process of using Mahout.GA for other problems. The  
> user will still need to design the solutions representation and to  
> implement a fitness function, but all the Hadoop stuff should be  
> hidden or at least made simpler;
> 5.Apply the generalized Mahout.GA to multiclass classification and  
> write a corresponding tutorial that explains how to use Mahout.GA to  
> solve new problems.
>
>
> IV. Success Criteria
>
> Main goals
>  1.Implement the parallelized fitness function described in [GA] and  
> validate its results on a small dataset;
>  2.Implement Mahout.GA for binary classification rule discovery. A  
> simpler (not parallelized) version of this algorithm should also be  
> implemented to     validate the results of Mahout.GA;
>
> Secondary goals
>  1.Allow the parallelized fitness function to be used independently  
> of Mahout.GA;
>  2.Use Mahout.GA on a different problem (multiclass classification)  
> and write a corresponding tutorial.
>
>
> V. Roadmap
>
> [April, 14: accepted students known]
>  1.Familiarize myself with Hadoop
>    Modify one of the examples of Hadoop to simulate an iterative  
> process. For each iteration, a new Job is executed with different  
> parameters, and its results are imported back by the program.
>  2.Implement the GA without parallelism
>    a.Start by implementing the tutorial example that comes with  
> WatchMaker;
>    b.Implement my own Individual and Fitness function classes;
>    c.Validate the algorithm using a small dataset, and find the  
> parameters that will give acceptable results.
>  3.Prepare whatever I may need in the development period
> [May, 26 coding starts]
>  4.Implement the parallelized fitness function
>    a.Use Hadoop Map-Reduce to implement it [2 weeks];
>    b.Validate it on a small dataset [1 week].
>  5.Implement Mahout.GA
>    a.Write an intermediary component between WatchMaker and the  
> parallelized fitness function. This component takes a population,  
> configures and launches a Job, waits for its end, then returns the  
> calculated fitness values [2 weeks];
>    b.Validate Mahout.GA by comparing its results with the GA without  
> parallelism [1 week].
> [July, 7-14 mid term evaluation]
>  6.Generic Mahout.GA
>    a.Identify the components that are problem dependant, and make  
> them less dependant of Hadoop as much as possible [2 weeks];
>    b.Implement the components for the multiclass classification  
> problem and validate Mahout.GA on a given dataset [2 week];
>    c.Write a tutorial that explains how to use Mahout.GA to solve  
> new problems (in this case the multiclass classification problem)  
> [in parallel with 5.b].
> [August, 11 suggested pencil 'down' date]
>  Clean the code and arrange the documentation.
> [August, 18 final evaluations]
>
> Note that this plan may change given my interaction with my Mentor  
> and the Mahout community.
>
> VI. Biography
>
> I am a PhD student at the University Mentouri of Constantine. My  
> primary research goal is a framework to help build Intelligent  
> Adaptive Systems. I am still on my first year, and there is a good  
> chance that I will be working on Distributed Evolutionary Algorithms  
> for the next three years.
>
> For the purpose of my Master, I worked on Artificial Immune Systems.  
> I applied them to handwritten digits recognition  
> [PatternRecognition] and Muliple Sequence Alignement  
> (bioinformatics) [BioInformatics]. I also built a feature selection  
> operator for Yale (but for lack of time I never published it), and  
> participated in an internship at the LIFL laboratory (Lille,  
> France), where I implemented several operators for a C++  
> evolutionary computation framework [ParadisEO].
>
> In parallel to my Master, I worked as a freelance programmer for my  
> University. I developed a Java scholar management system using  
> Eclipse, TortoiseSVN and many open source libraries. I gained a good  
> experience on project management (how to make a realistic plan and  
> stick to it) and open source development (how to choose a good open  
> source library, use it, and work around known bugs).
>
> VII. References
> [GA]    Bojarczuk CC, Lopes HS, and Freitas AA. "Discovering  
> comprehensible classification rules using genetic programming: a  
> case study in a medical domain". Proc. Genetic and Evolutionary  
> Computation Conference GECCO99, 953-958. Orlando, FL, USA, July 1999.
>
> [WatchMaker]    https://watchmaker.dev.java.net/
>
> [PatternRecognition]    S. Meshoul, A. Deneche, M. Batouche,  
> "Combining an Artificial Immune System with a Clustering Method for  
> Effective Pattern Recognition", International Conference on Machine  
> Intelligence ICMI’05, pp. 782-787, Tunis 2005.
>
> [BioInformatics]    A. Layeb, A. Deneche, "Multiple Sequence  
> Alignment by Immune Artificial System", ACS/IEEE International  
> Conference on Computer Systems and Applications AICCSA’07, Jordan  
> 2007.
>
> [ParadisEO]    http://paradiseo.gforge.inria.fr/index.php?n=Paradiseo.Home 
> ?from=Main.HomePage
>
> ----------------------------------------------------------------------------------------------
> This proposal is inspired from the excellent one of Konstantin Kafer  
> [http://drupal.org/files/application.pdf]
> *********************************************************************************************************
>
>
>
>      
> _____________________________________________________________________________
> Envoyez avec Yahoo! Mail. Capacité de stockage illimitée pour vos  
> emails. http://mail.yahoo.fr

Reply | Threaded
Open this post in threaded view
|

Re: GSoC Evolutionary Algorithm Proposal

Isabel Drost-3
+1

On Friday 28 March 2008, Grant Ingersoll wrote:

> +1
>
> On Mar 27, 2008, at 9:18 AM, deneche abdelhakim wrote:
> > I've written my proposal, and because I could no more change it
> > after I submit it to GSoc, I first post it here
> > if someone have some suggestions you are welcome.
> > I will wait until saturday morning to post it to the GSoC
> >
> > *************************************************************************
> >************* Application for Summer of Code 2008    Mahout Project
> >
> > Deneche Abdel Hakim
> >
> > Codename Mahout.GA
> >
> >
> > I. Synopsis
> >
> > I will add a genetic algorithm (GA) for binary classification on
> > large datasets to the Mahout project. To gain time I will use an
> > existing framework for genetic algorithms WatchMaker [WatchMaker]
> > with an Apache Software License. I will also add a parallelized
> > measure that indicates the quality of classification rules on a
> > given dataset, this measure will be available independently of the
> > GA. And if I have enough time I will make the GA more generic and
> > apply it on a different problem (multiclass classification).
> >
> >
> > II. Project
> >
> > A GA works by evolving a population of individuals toward a desired
> > goal. To get a satisfying solution, the GA needs to run thousands of
> > iterations with hundreds of individuals. For each iteration and
> > individual the fitness is calculated, it indicates the closeness of
> > that individual to the desired solution. The main advantage of GAs
> > is there ability to find solution of problems given only a fitness
> > measure (and of course a sufficient CPU power), this is particularly
> > helpful when the problem is complex and no mathematical solution is
> > available.
> >
> > My primary goal is to implement the GA described in [GA]. It uses a
> > fitness function that is easy to implement and can benefit from the
> > Map-Reduce strategy to exploit distributed computing (when the
> > training dataset is very large). It will be available as ready to
> > use tool (Mahout.GA) that discovers binary classification rules for
> > any given dataset. Concretely, the main program will launch the GA
> > using WatchMaker, each time the GA needs to evaluate the fitness of
> > the population it calls a specific class given by us, this class
> > will configure and launch a Hadoop Job on a distributed cluster.
> >
> > My secondary goal is to make Mahout.GA problem independent, thus
> > allowing us to use it for different problems such as multiclass
> > classification, optimization, clustering. This will be done by
> > implementing a ready to use generic fitness function for WatchMaker
> > that calls internally Hadoop. As a proof of concept I will use it
> > for multiclass classification (if I don't run out of time of course!).
> >
> >
> > III. Profit for Mahout
> >
> > 1.The GA will be integrated with Mahout as a ready to use rule
> > discovering tool for binary classification;
> > 2.Explore the integration of existing frameworks with Mahout, for
> > example how to design the program in a way that the framework
> > libraries will not be needed in the slave nodes (technically its
> > feasible, but I still need to learn how to do it);
> > 3.The parallelized fitness function can be used independently of
> > Mahout.GA. It’s a good measure of the quality of binary
> > classification rules;
> > 4.Simplify the process of using Mahout.GA for other problems. The
> > user will still need to design the solutions representation and to
> > implement a fitness function, but all the Hadoop stuff should be
> > hidden or at least made simpler;
> > 5.Apply the generalized Mahout.GA to multiclass classification and
> > write a corresponding tutorial that explains how to use Mahout.GA to
> > solve new problems.
> >
> >
> > IV. Success Criteria
> >
> > Main goals
> >  1.Implement the parallelized fitness function described in [GA] and
> > validate its results on a small dataset;
> >  2.Implement Mahout.GA for binary classification rule discovery. A
> > simpler (not parallelized) version of this algorithm should also be
> > implemented to     validate the results of Mahout.GA;
> >
> > Secondary goals
> >  1.Allow the parallelized fitness function to be used independently
> > of Mahout.GA;
> >  2.Use Mahout.GA on a different problem (multiclass classification)
> > and write a corresponding tutorial.
> >
> >
> > V. Roadmap
> >
> > [April, 14: accepted students known]
> >  1.Familiarize myself with Hadoop
> >    Modify one of the examples of Hadoop to simulate an iterative
> > process. For each iteration, a new Job is executed with different
> > parameters, and its results are imported back by the program.
> >  2.Implement the GA without parallelism
> >    a.Start by implementing the tutorial example that comes with
> > WatchMaker;
> >    b.Implement my own Individual and Fitness function classes;
> >    c.Validate the algorithm using a small dataset, and find the
> > parameters that will give acceptable results.
> >  3.Prepare whatever I may need in the development period
> > [May, 26 coding starts]
> >  4.Implement the parallelized fitness function
> >    a.Use Hadoop Map-Reduce to implement it [2 weeks];
> >    b.Validate it on a small dataset [1 week].
> >  5.Implement Mahout.GA
> >    a.Write an intermediary component between WatchMaker and the
> > parallelized fitness function. This component takes a population,
> > configures and launches a Job, waits for its end, then returns the
> > calculated fitness values [2 weeks];
> >    b.Validate Mahout.GA by comparing its results with the GA without
> > parallelism [1 week].
> > [July, 7-14 mid term evaluation]
> >  6.Generic Mahout.GA
> >    a.Identify the components that are problem dependant, and make
> > them less dependant of Hadoop as much as possible [2 weeks];
> >    b.Implement the components for the multiclass classification
> > problem and validate Mahout.GA on a given dataset [2 week];
> >    c.Write a tutorial that explains how to use Mahout.GA to solve
> > new problems (in this case the multiclass classification problem)
> > [in parallel with 5.b].
> > [August, 11 suggested pencil 'down' date]
> >  Clean the code and arrange the documentation.
> > [August, 18 final evaluations]
> >
> > Note that this plan may change given my interaction with my Mentor
> > and the Mahout community.
> >
> > VI. Biography
> >
> > I am a PhD student at the University Mentouri of Constantine. My
> > primary research goal is a framework to help build Intelligent
> > Adaptive Systems. I am still on my first year, and there is a good
> > chance that I will be working on Distributed Evolutionary Algorithms
> > for the next three years.
> >
> > For the purpose of my Master, I worked on Artificial Immune Systems.
> > I applied them to handwritten digits recognition
> > [PatternRecognition] and Muliple Sequence Alignement
> > (bioinformatics) [BioInformatics]. I also built a feature selection
> > operator for Yale (but for lack of time I never published it), and
> > participated in an internship at the LIFL laboratory (Lille,
> > France), where I implemented several operators for a C++
> > evolutionary computation framework [ParadisEO].
> >
> > In parallel to my Master, I worked as a freelance programmer for my
> > University. I developed a Java scholar management system using
> > Eclipse, TortoiseSVN and many open source libraries. I gained a good
> > experience on project management (how to make a realistic plan and
> > stick to it) and open source development (how to choose a good open
> > source library, use it, and work around known bugs).
> >
> > VII. References
> > [GA]    Bojarczuk CC, Lopes HS, and Freitas AA. "Discovering
> > comprehensible classification rules using genetic programming: a
> > case study in a medical domain". Proc. Genetic and Evolutionary
> > Computation Conference GECCO99, 953-958. Orlando, FL, USA, July 1999.
> >
> > [WatchMaker]    https://watchmaker.dev.java.net/
> >
> > [PatternRecognition]    S. Meshoul, A. Deneche, M. Batouche,
> > "Combining an Artificial Immune System with a Clustering Method for
> > Effective Pattern Recognition", International Conference on Machine
> > Intelligence ICMI’05, pp. 782-787, Tunis 2005.
> >
> > [BioInformatics]    A. Layeb, A. Deneche, "Multiple Sequence
> > Alignment by Immune Artificial System", ACS/IEEE International
> > Conference on Computer Systems and Applications AICCSA’07, Jordan
> > 2007.
> >
> > [ParadisEO]  
> > http://paradiseo.gforge.inria.fr/index.php?n=Paradiseo.Home
> > ?from=Main.HomePage
> >
> > -------------------------------------------------------------------------
> >--------------------- This proposal is inspired from the excellent one of
> > Konstantin Kafer [http://drupal.org/files/application.pdf]
> > *************************************************************************
> >********************************
> >
> >
> >
> >
> > _________________________________________________________________________
> >____ Envoyez avec Yahoo! Mail. Capacité de stockage illimitée pour vos
> > emails. http://mail.yahoo.fr


--
I'm not under the alkafluence of inkaholthat some thinkle peep I am.It's just
the drunker I sit here the longer I get.
  |\      _,,,---,,_       Web:   <http://www.isabel-drost.de>
  /,`.-'`'    -.  ;-;;,_
 |,4-  ) )-,_..;\ (  `'-'
'---''(_/--'  `-'\_) (fL)  IM:  <xmpp://[hidden email]>

signature.asc (196 bytes) Download Attachment