Harmony Search Algorithmus

Bei vielen existierende Problemen handelt es sich um Optimierungsprobleme. Um diese zu lösen, können traditionelle mathematische Techniken angewendet werden. Diese Techniken haben jedoch ihre Nachteile bei der praktischen Anwendung. Globale Optimas werden zwar ermittelt, jedoch ohne Beachten der Laufzeit des Algorithmus. Allein durch eine Erhöhung der zu betrachtenden Variablen eines Problems könnte die Laufzeit so stark ansteigen, dass ein Auswerten in annehmbarer Zeit nicht mehr möglich ist (Fluch der Dimensionalität). Denkbar wären auch Fälle, wo eine Funktion für die Bestimmung des globalen Optimums nicht differenzierbar ist. Auch dann könnte die mathematische Technik kein Ergebnis liefern.

Der Algorithmus der hier vorgestellt werden soll ist Harmony Search. Er wurde von Dr. Zong Woo Geem entwickelt und ist ein recht neuer Algorithmus (erschienen im Jahr 2000). Wie viele andere metaheuristische Algorithmen hat auch Harmony Search seinen Ansatz im Nachbilden von Vorgängen aus der Natur. Er stammt aus den Bereichen „Soft Computing“ und „Evolutionäre Algorithmen“ und wurde durch den Prozess des Improvisierens unter Musikern inspiriert. Jeder Musiker spielt eine Note und alle Musiker zusammen versuchen eine beste Harmonie zu erreichen.

Harmony Search Präsentation

Ich habe den Harmony Search Algorithmus in Java implementiert und auf die bekannte Rosenbrock Funktion angewandt die oft für Optimierungsprobleme verwendet wird. Die Rosenbrock Funktion ist wie folgt definiert:

f(x, y) = (1 − x)^2 + 100 ∗ (y − x^2)^2

Ihr globales Minimum befindet sich bei x=-1 und y=+1. Der komplette Java Code zu dem Programm ist wie folgt ersichtlich.

public class HarmonySearch extends Applet {

  private static final long serialVersionUID = 6236612830049354789L;
  private static int HMS = 10;
  private static double HMCR = 0.9;
  private static double PAR =  0.3;
  private static int number_of_improvisations = 90000;
  private static int N = 2;

  private Random rand = new Random(System.currentTimeMillis());
  private SolutionVector bestVector = null;

  public class SolutionVector
  {
    public Float[] decisionVariables;
    public Float objectiveFunctionValue;
  } 

  private Float objectiveFunction(SolutionVector vector)
  {
    Float x1 = vector.decisionVariables[0];
    Float x2 = vector.decisionVariables[1];

    // minimize the rosenbrock function
    return (1-x1*x1)*(1-x1*x1)+ 100*(x2-x1*x1)*(x2-x1*x1);
  }

  public float getRandomValue()
  {
    // get random float value between -2 and +2
    Float value = ((Integer)rand.nextInt(4)).floatValue();
    value = value -2;
    value = value + rand.nextFloat();
    return value;
  }

  private Float getDecisionVariableFromHarmonyMemory(SolutionVector[] harmonyMemory, int decisionVariableIndex)
  {
    Float[] candidates = new Float[HMS];
    for (int i=0; i< HMS; i++)
    {
      candidates[i] = harmonyMemory[i].decisionVariables[decisionVariableIndex];
    }

    // return a randomly chosen decision variable from
    // the harmonyMemory for a specified
    // decision variable index
    return candidates[rand.nextInt(HMS)];
  }

  public Boolean isRandomSelection()
  {
    // check with probability, if the new decision
    // variable will be random or from the harmony memory
    Float value = rand.nextFloat();
    if (value < HMCR)
      return false;
    else
      return true;
  }

  public Boolean isPitchAdjustment()
  {
    // check with probability, if the new decision
    // variable should be pitched
    Float value = rand.nextFloat();
    if (value < PAR)
      return false;
    else
      return true;
  } 

  public void init()
  {
    MouseInputAdapter mouseListener = new MouseInputAdapter() {
          public synchronized void mouseClicked(MouseEvent event)
          {
            if (event.getSource() instanceof JButton)
            {
              startHarmonySearch();
              repaint();
              return;
            }
          }
        };

        setSize(360, 100);
        this.addMouseListener(mouseListener);
        this.setLayout(new BorderLayout());

        JPanel rightPanel = new JPanel();
        JButton button = new JButton();
        button.setText("Start Harmony Search");
        button.addMouseListener(mouseListener);
        rightPanel.add(button);
        this.add(rightPanel,BorderLayout.NORTH);

        startHarmonySearch();
  }

  private void startHarmonySearch()
  {
    bestVector = new SolutionVector();

    // 1. create and initialize harmony memory

    SolutionVector[] harmonyMemory = new SolutionVector[HMS];
    for (int i=0; i < HMS; i++)
    {
      harmonyMemory[i] = new SolutionVector();
      harmonyMemory[i].decisionVariables = new Float[N];

      for (int j=0; j < N; j++)
        harmonyMemory[i].decisionVariables[j] = getRandomValue();

      harmonyMemory[i].objectiveFunctionValue = objectiveFunction(harmonyMemory[i]);
    }   

    // 2. improvise new harmony vector
    int count = 0;
    while (count < number_of_improvisations)
    {
      count++;

      SolutionVector improvise = new SolutionVector();
      improvise.decisionVariables = new Float[N];

      // create decision variables of new harmony vector
      for (int i=0; i<N; i++)
      {
        if (isRandomSelection())
        {
          // case 1: random selection
          improvise.decisionVariables[i] = getRandomValue();
        }
        else
        {
          // case 2: hm consideration
          improvise.decisionVariables[i] = getDecisionVariableFromHarmonyMemory(harmonyMemory, i);

          if (isPitchAdjustment())
          {
            // pitch adjustment +1 or -1
            if (rand.nextBoolean())
              improvise.decisionVariables[i] = improvise.decisionVariables[i] + 0.0000001F;
            else
              improvise.decisionVariables[i] = improvise.decisionVariables[i] - 0.0000001F;
          }
        }
      }

      // get the objective function value for the new
      // improvised harmony vector

      improvise.objectiveFunctionValue = objectiveFunction(improvise);

      // harmony memory update. If the new improvised vector
      // is better than the worst vector in the harmony memory,
      // keep the new vector and drop the old

      Float worstValue = 0F;
      int worstVectorPos = 0;
      for (int i=0; i < HMS; i++)
      {
        if (harmonyMemory[i].objectiveFunctionValue > worstValue)
        {
          worstValue = harmonyMemory[i].objectiveFunctionValue;
          worstVectorPos = i;
        }
      }

      if (improvise.objectiveFunctionValue < worstValue)
      {
        harmonyMemory[worstVectorPos] = improvise;
        bestVector = improvise;
      }
    }   

  }

  @Override
  public void paint(Graphics g)
  {
    Graphics2D g2 = (Graphics2D) g;
    super.paint(g2);

    g2.setColor(Color.BLACK);

    // sämtliche Punkte für beide Klassen zeichnen

    if (bestVector != null)
      g2.drawString("X: " + bestVector.decisionVariables[0] + " | Y: " +
          bestVector.decisionVariables[1] + " - Result: " +
          bestVector.objectiveFunctionValue,20,60 );
  }
}
comments powered by Disqus