Sunday, July 27, 2008

TRSeeMe


No wreszcie uporałem się z konfiguracją czytnika Google więc mogę się zająć przedstawieniem rzeczy dla mnie ważnych...

W swojej pracy magisterskiej pod tytułem "Optymalizacja rozmieszczenia stacji bazowych i ich parametrów w systemie radiokomunikacji ruchomej lądowej" zająłem się praktycznym wykorzystaniem algorytmów genetycznych w języku C++.

Należałoby podkreślić, że rozwój systemów telekomunikacyjnych umożliwia tworzenie podstaw społeczeństwa informacyjnego, a projektowanie konkretnych
realizacji systemów jest procesem bardzo złożonym i czasochłonnym. W pracy dyplomowej zbadałem możliwości optymalizacji rozmieszczenia stacji bazowych i wysokości zawieszenia ich anten w systemach radiokomunikacji ruchomej lądowej.
W części teoretycznej pracy omówiłem zagadnienia związane z modelowaniem propagacji fal elektromagnetycznych w systemach radiokomunikacji ruchomej lądowej oraz przedstawiłem reguły stosowane przy rozmieszczaniu stacji bazowych w tych systemach na przykładzie systemu GSM (Global System for Mobile communications). Omówiłem także podstawy teoretyczne metod służących do wyznaczania tzw. zasięgów optycznych oraz metod wykorzystywanych do optymalizacji, w których zastosowano algorytmy genetyczne.
W celu optymalizacji rozmieszczenia stacji bazowych i wysokości zawieszenia
ich anten w systemie  radiokomunikacji ruchomej lądowej napisałem program TRSeeMe
realizujący wiele funkcji użytkowych (dostępny w językach: polskim, angielskim i francuskim z możliwością dynamicznego ich przełączania). Przed rozpoczęciem obliczeń wymagane jest wprowadzenie odpowiednio sformatowanych danych dotyczących ukształtowania terenu.
Przy optymalizacji zastosowałem kryterium bezpośredniej widoczności optycznej pomiędzy
anteną odbiorczej stacji ruchomej, a anteną bazowych stacji nadawczych.
W programie wykorzystałem mechanizmy programowania obiektowego (Object Oriented
Programming) dostępne w języku C++. W jednej z  procedur optymalizacyjnych
zastosowałem klasyczny algorytm genetyczny.
W rozdziale czwartym rozważałem sytuację teoretyczną, w której w systemie istnieje
tylko jedna stacja bazowa i bada się jaki obszar jest widoczny w każdym punkcie terenu.
Program optymalizuje rozmieszczenie stacji bazowej wybierając miejsce (trzema różnymi
metodami), z którego widać procentowo najwięcej pozostałych punktów badanego terenu.
Program podaje odpowiedź w postaci odpowiedniego raportu oraz umożliwia odpowiednią
prezentację wyników w postaci graficznej.
W rozdziale piątym omówiłem sytuację, w której system składa się z trzech
stacji bazowych (jest to wtedy tzw.  system wielostrefowy), podane są parametry stacji
bazowych, które mają podlegać optymalizacji  oraz dane są przedziały w jakich te parametry
mają być optymalizowane. Program optymalizuje rozmieszczenie stacji wykorzystując
algorytm genetyczny i podaje odpowiedź w postaci odpowiedniego raportu oraz w formie
graficznej.
Wyniki zastosowanych metod optymalizacyjnych (w rozdziałach czwartym i piątym)
posłużyły następnie do przeprowadzenia symulacji rozkładu natężenia pola (składowej
elektrycznej pola elektromagnetycznego) oraz rozkładu mocy za pomocą specjalistycznej
aplikacji R-Model. W pracy przedstawiłem wyniki dla dwóch systemów: z jedną stacją
bazową oraz z trzema (wszystkie o tej samej wysokości zawieszenia ich anteny
nadawczej równej 20 m). Wysokość zawieszenia stacji ruchomej była określona na 2 m.
Na podstawie wyników (w postaci graficznej) stwierdziłem występowanie różnic
w określaniu zasięgów optycznych uzyskiwanych dla stacji bazowych za pomocą
obu programów (R-Model i TRSeeMe). Zauważyłem jednak, że występowanie tych różnic
nie powoduje uzyskiwania niezadawalających rezultatów dla metod optymalizacyjnych.
Otrzymywane rozwiązania dla różnych typów cyfrowych map terenu za pomocą
programu TRSeeMe są bliskie rozwiązaniom optymalnym (pomimo występowania
różnic w wyznaczaniu bezpośredniej widoczności optycznej).

Celem pracy dyplomowej było zaproponowanie skutecznej metody optymalizacji rozmieszczenia stacji bazowych i wysokości zawieszenia ich anten w systemach radiokomunikacji ruchomej lądowej. Udało mi się osiągnąć ten cel opracowując takie narzędzie programowe, które pozwala projektantowi takich systemów skrócić czas  i zmniejszyć nakłady pracy potrzebne do osiągnięcia zadowalających rozwiązań w projektowaniu i realizacji współczesnych systemów radiokomunikacji ruchomej.

Polecam rewelacyjną książkę "Algorytmy genetyczne struktury danych programy ewolucyjne" (Zbigniew Michalewicz), która natchnęła mnie do napisania TRSeeMe.

Główna pętla klasycznego algorytmu genetycznego wygląda w TRSeeMe następująco:

while(GEN_Generation < GEN_MAXGENS){
      GEN_Generation++;
      if (GEN_IfPoweredSelection==YES) //jest znane z dialogu
          GEN_SelectPowered(Population, NewPopulation, GEN_Power);
        else
          GEN_SelectRWheel(Population, NewPopulation);
      GEN_CrossOver(Population);
      GEN_Mutate(Population);
      GEN_Evaluate(Population, IfSlowMethod);
      GEN_Elitist(Population);
      GEN_Report(streamFile2, GEN_Generation, Population);
      GEN_XLSRprt(streamFile3, GEN_Generation, Population);
}

Przy oszacowywaniu funkcji celu wyznaczam dopasowanie w następujących etapach:

   double sum = 0;
   int mem;
   // wyznaczanie całkowitego dopasowania populacji
   for (mem =0; mem < GEN_POPSIZE; mem++)
     {
        sum += Population[mem].Fitness;
     }

   // wyznaczanie dopasowania względnego = prawdopodobieństwo selekcji chromosomu mem: ps(mem)
   for (mem =0; mem < GEN_POPSIZE; mem++)
     {
        Population[mem].rFitness = (double)(Population[mem].Fitness)/sum;
     }
   Population[0].cFitness = Population[0].rFitness;

   // wyznaczanie dopasowania łącznego => na kole ruletki określane są wycinki koła
   for (mem =1; mem < GEN_POPSIZE; mem++)
     {
        Population[mem].cFitness = Population[mem-1].cFitness +Population[mem].rFitness;
     }

Dzięki takiemu algorytmowi TRSeeMe usyskuje całkiem niezłe rezultaty stosując trzy metody wyznaczania zasięgu: wolną (bez pamięci co odkrył), szybką (z zapamiętywaniem historii obliczeń) i kompromis pomiędzy nimi!

Teraz nadszedł czas, żeby zastosować algorytm genetyczny w Javie! A czy wiecie, że Java nazywała się OAK (ang. DĄB)?

Repetitio est mater studiorum (Powtarzanie jest matką wiedzy)...

Zacznę jednak od tworzenia najprostszego POJO:

package com.kdabrowski.beanmaster;

public class Person implements java.io.Serializable {
  protected String firstName;
  protected String lastName;
  protected int age;

  public Person() {
  }

  public String getFirstName() {
    return firstName;
  }
  public void setFirstName(String aFirstName) {
    firstName = aFirstName;
  }

  public String getLastName() {
    return lastName;
  }

  public void setLastName(String aLastName) {
    lastName = aLastName;
  }

  public int getAge() {
    return age;
  }
  public void setAge(int anAge) {
    age = anAge;
  }
}


W tym celu zapiszemy w pliku web.xml:

<?xml version="1.0" encoding="UTF-8"?>
<web-app version="2.4"
            xmlns="http://java.sun.com/xml/ns/j2ee"
            xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
            xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee
            http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd">
  <servlet>
        <servlet-name>BrainServlet</servlet-name>
        <servlet-class> com.kdabrowski.beanmaster.BrainServlet</servlet-class>
    </servlet>
    <servlet-mapping>
        <servlet-name>BrainServlet</servlet-name>
        <url-pattern>/BrainServlet</url-pattern>
    </servlet-mapping>
    <session-config>
        <session-timeout>
            30
        </session-timeout>
    </session-config>
  <welcome-file-list>
    <welcome-file>index.jsp</welcome-file>
  </welcome-file-list>
</web-app>


I napiszemy najprostszą implementację servletu HttpServlet:

package com.kdabrowski.beanmaster;

import java.io.*;
import javax.servlet.*;
import javax.servlet.http.*;

public class BrainServlet extends HttpServlet {

            static final long serialVersionUID = 1L;
           
    public void doGet(HttpServletRequest request, HttpServletResponse response)
    throws IOException, ServletException
    {
        response.setContentType("text/html");
        PrintWriter out = response.getWriter();
        out.println("<html>");
        out.println("<head>");
        out.println("<title>Hello World!</title>");
        out.println("</head>");
        out.println("<body>");
        out.println("<h1>Hello World! This is BrainServlet!</h1>");
        out.println("</body>");
        out.println("</html>");
    }
}

 Główna pętla mojego klasycznego algorytmu genetycznego może tutaj wyglądać następująco:

  private runG33Genetics(void){
   
        while(g33Generation < g33MAXGENS){
            g33Generation++;
            if (g33IfPwrdSlction==YES) //jest znane z dialogu
                g33SelectPowered(Population, g33NewPopulation, g33Power);
            else
                g33SelectRWheel(Population, g33NewPopulation);
            g33CrossOver(Population);
            g33Mutate(Population);
            g33Evaluate(Population, IfSlowMethod);
            g33Elitist(Population);
            g33Report(streamFile2, g33Generation, g33Population);
            g33
XLSRprt(streamFile3, g33Generation, g33Population);

        }
    }    

Natomiast wybór najlepszego osobnika zaczynam następująco:

private g33Elitist(G33Genotype[] g33Population)
{
   int i;
   double best, worst; // najlepsza i najgorsza wartość dopasowania
   int best_mem, worst_mem; // wsk. najlepszego i najgorszego osobnika

   best = g33Population[0].dFitness;
   worst = g33Population[0].dFitness;
   for (i=0; i < g33POPSIZE-1; i++)
     {
       if (g33Population[i].dFitness > g33Population[i+1].dFitness)
         {
           if (g33Population[i].dFitness >= best)
             {
               best = g33Population[i].dFitness;
               best_mem = i;
             }
           if (g33Population[i+1].dFitness <= worst)
             {
               worst = g33Population[i+1].dFitness;
               worst_mem = i+1;
             }
         }
         else
         {
           if (g33Population[i].dFitness <= worst)
             {
               worst = g33Population[i].dFitness;
               worst_mem = i;
             }
           if (g33Population[i+1].dFitness >= best)
             {
               best = g33Population[i+1].dFitness;
               best_mem = i+1;
             }
         }
     }

(...)

25 lipca 2008 to moje imieniny. To były naprawdę
najgorętsze imieniny od wieków. Dzięki za wszystkie życzenia!

Postanowiłem zaprzestać prowadzenia blogów jednocześnie po polsku i angielsku na bliźniaczych blogach, na których rozpocząłem tę zabawę w 2007 roku (pozostanie jedynie http://kdabrowski.blogspot.com):

http://kjdabrowski.blogspot.com

http://grathor33.blogspot.com

No comments: