Roulette Wheel Selection Algorithm

Hallo,

da ich mich gerade mit genetischen Algorithmen beschäftige, ist dabei ein netter Algorithmus abgefallen:

Roulette Wheel Selection* Eine mit Objekten gefüllte Liste, wobei jedem Eintrag ein bestimmter Fitness Score zugewiesen ist

• Wenn man sich nun ein Objekt zurückgeben lässt, so wird wahrscheinlich jenes genommen welches den höchsten Fitness Score hat (Die wahrscheinlichkeit ist proportional zu seinem Score)

Siehe: http://en.wikipedia.org/wiki/Fitness_proportionate_selection

/*
 * Roulette Wheel Algorithm (aka Fitness proportionate selection)
 * See: [URL]http://en.wikipedia.org/wiki/Fitness_proportionate_selection[/URL]
 * 
 * March 2008 Egon A. Rath 
 *
 */

using System;
using System.Text;
using System.Collections.Generic;

namespace egrath.tools.algo
{
	public class RouletteWheelSelection<T>
	{
		private List<RouletteItem> m_Items;
		private Random m_RandomGenerator = new Random();

		public RouletteWheelSelection()
		{
			m_Items = new List<RouletteItem>();
		}

        /// <summary>
        /// Adds a new Item to the Wheel
        /// </summary>
        /// <param name="item"></param>
        /// <param name="score"></param>
		public void Add( T item, double score )
		{
			m_Items.Add( new RouletteItem( item, m_Items.Count == 0 ? 0 : m_Items[m_Items.Count-1].TotalScore + score, score ));
		}

        /// <summary>
        /// Returns a Item according to the Roulette Wheel Algorithm
        /// </summary>
        /// <returns>Selected Item</returns>
		public T GetItem( bool remove )
		{
            if( m_Items.Count == 0 )
                return default( T );

			int select = m_RandomGenerator.Next(( int ) m_Items[m_Items.Count-1].TotalScore );
			for( int index = 0; index < m_Items.Count; index ++ )
			{
                double lowerLimit = 0;
                if( index > 0 )
                    lowerLimit = m_Items[index-1].TotalScore;

                double upperLimit = m_Items[index].TotalScore;

				if( select >= lowerLimit && select <= upperLimit )
                {
                    T item = m_Items[index].Item;
                    if( remove )
                    {
                        RemoveItem( index );
                    }

					return item;
                }
			}

			throw( new Exception( "RouletteWheelSelection internal error!" ));
        }

        /// <summary>
        /// Number of Items contained within the Wheel
        /// </summary>
        public int NumItems
        {
            get { return m_Items.Count; }
        }

        /// <summary>
        /// Internal usage: Removes the Item at the specified index from the Wheel
        /// </summary>
        /// <param name="index"></param>
        private void RemoveItem( int index )
        {
            double baseScore = m_Items[index].TotalScore - m_Items[index].ItemScore;
            m_Items.RemoveAt( index );
            for( int i = index; i < m_Items.Count; i ++ )
            {
                m_Items[index].TotalScore = baseScore + m_Items[index].ItemScore;
                baseScore = m_Items[index].TotalScore;
            }
        }

#if DEBUG
        public void DumpProbability()
        {
            double total = m_Items[m_Items.Count-1].TotalScore;

            foreach( RouletteItem item in m_Items )
            {
                Console.Out.WriteLine( "Item: [{0}], Score = {1}, Probability = {2:F4}%",
                    item.Item,
                    item.ItemScore,
                    ( 100 / total ) * item.ItemScore );
            }
        }
#endif

        #region Roulette Item
        private class RouletteItem
		{
			private T m_Item;
            private double m_ItemScore;
			private double m_TotalScore;

			public RouletteItem( T item, double score, double itemScore )
			{
				Item = item;
				TotalScore = score;
                ItemScore = itemScore;
			}

			public T Item
			{
				get
				{
					return m_Item;
				}

				set
				{
					m_Item = value;
				}
			}

            public double ItemScore
            {
                get
                {
                    return m_ItemScore;
                }

                set
                {
                    m_ItemScore = value;
                }
            }

			public double TotalScore
			{
				get
				{
					return m_TotalScore;
				}

				set
				{
					m_TotalScore = value;
				}
			}
        }
        #endregion
    }

	public class RouletteTest
	{
		public static void Main( string[] args )
		{
			RouletteWheelSelection<string> rws = new RouletteWheelSelection<string>();

            char[] c = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
                                    'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
            Random rnd = new Random();
            for( int cnt = 0; cnt < c.Length; cnt ++ )
            {
                rws.Add( new string( c[cnt], 10 ), cnt+1 );
            }

#if DEBUG
            rws.DumpProbability();
#endif

			for( int i = 0; i < 30; i ++ )
            {                
                string item = rws.GetItem( false );
                if( item != default( string ))
				    Console.Out.WriteLine( item );
                else
                {
                    Console.Out.WriteLine( "No more items!" );
                    break;
                }
            }
		}
	}
}

Vielleicht kanns ja jemand ausser mir brauchen 😉

Grüsse,
Egon