Algorytm genetyczny pomoc

Algorytm genetyczny pomoc
AL
  • Rejestracja:ponad 4 lata
  • Ostatnio:około 4 lata
  • Postów:3
0

Mam na zadanie taki program i utknąłem w martwym punkcie.
Napisać program symulujący ewolucję populacji osobników. Populacja może liczyć dowolną liczbę osobników. Każdy osobnik zawiera chromosom, który jest ciągiem liczb naturalnych. Chromosomy mogą być różnej długości. W każdym pokoleniu wylosowywanych jest k par osobników, które się następnie krzyżują. Krzyżowanie polega na tym, że u każdego osobnika dochodzi do pęknięcia chromosomu w dowolnym miejscu. Część początkowa chromosomu jednego osobnika łączy się z częścią końcową drugiego. Inaczej mówiąc: osobniki wymieniają się fragmentami swoich chromosomów. Jeden osobnik może być wylosowany do kilku krzyżowań. Po dokonaniu wszystkich krzyżowań w pokoleniu sprawdzane jest przystosowanie osobników do warunków środowiska. W tym celu dla każdego osobnika wyznaczana jest wartość f ∈ [0, 1] funkcji dopasowania.
Plik wejściowy ma następującą postać: Każda linia zawiera jednego osobnika. Osobnik charakteryzowany jest chromosomem, który jest przedstawiony jako ciąg liczb naturalnych rozdzielonych białymi znakami. Przykładowy plik wejściowy zawierający populację złożoną z czterech osobników:
8 2 56 9 8 6 25 45
6 92 43 7 98
2 4 34 5
23 66 22 8 34 6 1 6 8 7 88

Jedynie co mam to wypisywanie plików. Dalej nie mam pomysłu na losowanie i dzielenie.

Kopiuj
#include <iostream>
#include <vector>
#include <string>
#include<sstream>
#include <fstream>
using namespace std;
struct osoba
{
	vector<int> frag;

};
int main()
{
	odczyt();

}
void odczyt()
{
	fstream plikw;
	plikw.open("Plik txt chrom.txt");
	if (plikw.good() == false) cout << "Plki jest w zlym folderze, lub nie istnieje";
	vector<osoba> chromosom;
	for (string line; getline(plikw, line); cout << endl)
	{
		stringstream stem(line);
		chromosom.emplace_back();
		for (int temp; stem >> temp; cout << temp << ' ') chromosom.back().frag.push_back(temp);
	}
	plikw.close();
}
void mieszanie()
{
 ???????
}

Prosiłbym o pomoc i wyjaśnienie.
Ma to działać na vektorach i strukturze osoba.

edytowany 1x, ostatnio: kq
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:2 minuty
2
  1. Fajnie, ale w treści zadania nie ma funkcji celu (którą trzeba zoptymalizować).
    Jest o tyle dobrze, że jest wspomniana jako "funkcja dopasowania".
    Bez tego nic nie "wylosujesz" bo nie masz danych do tego potrzebnych.
  2. nie ma nic o mutacjach
  3. "osoba" != "osobnik"
  4. zamiast void mieszanie() napisz Osobnik krzyzuj(const Osobnik&a, const Osobnik& b). Swoją drogą to problem jest postawiony na głowie, bo zwykle funkcję krzyżowania się samemu dobiera, gdy znana jest funkcja dopasowania (funkcja krzyżowania ma być mało szkodliwa dla wyniku dopasowania).
  5. reszta rad, po tym jak ponaprawiasz 1-4.

Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 4x, ostatnio: MarekR22
AL
  • Rejestracja:ponad 4 lata
  • Ostatnio:około 4 lata
  • Postów:3
0

funkcji dopasowania. Osobniki, dla których wartość f < w (gdzie w jest progiem wymierania), są usuwane z populacji. Osobniki, dla których f > r (gdzie r jest progiem rozmnażania) są klonowane. A osobniki, dla których w <= f <= r pozostają w populacji, ale się nie rozmnażają.

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include<sstream>
#include<time.h>
struct osobnik
{
std::vector<int> allel;

};
void wczytywanie()
{
std::fstream plik;
plik.open("Chromosom.txt");
if (plik.good() == false) std::cout << "Plki jest umieszczony w zlym folderze, lub nie istnieje";
std::vector<osobnik> chromosom;
std::cout << "Wszytkie osobniki : \n\n";
for (std::string line; getline(plik, line); std::cout << std::endl)
{
std::stringstream ss(line);
chromosom.emplace_back();
for (int temp; ss >> temp; std::cout << temp << ' ') chromosom.back().allel.push_back(temp);
}
std::cout << "\n\nilosc elementow vektora : " << chromosom.size();
plik.close();
}

osobnik krzyzuj(const osobnik& a, const osobnik& b)
{

}

int main()
{
wczytywanie();

}

Tasmanian Devil
Hej! Twój post prawdopodobnie zawiera niesformatowany kod. Użyj znaczników ``` aby oznaczyć, co jest kodem, będzie łatwiej czytać. (jestem botem, ta akcja została wykonana automatycznie, prawdopodobieństwo 0.99532217)
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:2 minuty
0
Alphaaa napisał(a):

funkcji dopasowania. Osobniki, dla których wartość f < w (gdzie w jest progiem wymierania), są usuwane z populacji. Osobniki, dla których f > r (gdzie r jest progiem rozmnażania) są klonowane. A osobniki, dla których w <= f <= r pozostają w populacji, ale się nie rozmnażają.

To nie jest definicja funkcji dopasowania! Ale jakaś kulawa wersja jak taka funkcja może być wykorzystana (kulawa wersja algorytmu genetycznego).
Funkcja dopasowania w kodzie ma taki prototyp:

Kopiuj
double jakDobrzeSobieRadziOsobnik(const osobnik& o)
{
      return ....;
}

Np może to być długość jaką pokona sprzedawca odwiedzający wszystkie miasta (problem komiwojażera).
Jeśli nie masz definicji f (jaka wartość f jest obliczona dla osobnika), to jedynie co możesz zrobić to napisać abstrakcję algorytmu genetycznego (wzorzec strategia), ale w tej chwili (i przez najbkliższe X lat) jest to poza twoim zasięgiem. Zadanie wygląda na coś konkretnego, ergo musisz gdzieś mieć definicję f.

Tak jak już wspomniałem f jest najważniejszym elementem algorytmu genetycznego. To on stanowi definicję problemu do rozwiązania.
To do f dobiera się wszystko inne, od opisu osobnika (chromosomu), przez operator krzyżowania, po operator mutacji.
Bez f (funkcji dopasowania) nie ma szans byś rozwiązał zadanie.
Jeśli autor zadania opisał wszystko poza funkcją dopasowania, to znaczy, że sam nie rozumie co robi algorytm genetyczny. Ja stawiam na to, że masz dziurę w notatkach.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22
katakrowa
  • Rejestracja:około 10 lat
  • Ostatnio:około 2 lata
  • Lokalizacja:Chorzów
  • Postów:1670
1

Jaki jest cel Twojego tego algorytmu? Co chcesz osiągnąć?
Po co oni się mają krzyżować jakie są pożądane cechy "osobnika" docelowego?
Innymi słowy jakie cechy ma spełniać ciąg liczb naturalnych osobnika, który jest najlepszy?


Projektowanie i programowanie. Hobbystycznie elektronika i audio oszołom.
_13th_Dragon
On chce zaliczyć najmniejszym wysiłkiem.
stivens
  • Rejestracja:ponad 8 lat
  • Ostatnio:około 5 godzin
0

@MarekR22: a to nie jest tak, ze dopasowanie to wartosc osobnika (liczona funkcja celu) wzgledem populacji?


λλλ
edytowany 1x, ostatnio: stivens
MarekR22
dokładnie on ma to w treści opisane jako "dopasowanie" a nie ma definicji tego.
stivens
Nie musi miec definicji jesli byla na wykladzie
stivens
Znaczy inaczej. Wzor na dostosowanie gosc powinien znac a funkcja celu powinna byc podana
MarekR22
Moderator C/C++
  • Rejestracja:około 17 lat
  • Ostatnio:2 minuty
1

Algorytm genetyczny stosuje się do problemów, gdzie masz funkcję celu i szukasz minimum tej funkcji.
To jest miękka metoda szukania minimum jakiejś funkcji i stosuje się ją w momencie, gdzie klasyczne metody (jak metoda Newtona) jest zbyt skomplikowana lub nieefektywna (bo np liczba zmiennych jest za duża).

Daną wejściową zawsze jest funkcja którą chcemy minimalizować.
Wyjściem ma być argument, dla którego ta funkcja daje wartość minimalną.

Klasyczne przykłady:

  • szukanie najkrótszej drogi w problemie komiwojażera - funkcja celu opisuję drogę jaką pokonuje sprzedawca
  • problem minimalnego rozkroju - funkcja celu to ilość odpadów
  • skręcanie białek - funkcja celu to energia potencjalna molekuły

Nie mając funkcji celu/dopasowania/długości drogi czy jakikolwiek to nazwać, nie ma problemu do rozwiązania.

Ergo treść tego zadania, wygląda jak lista podpowiedzi do implementacji algorytmu, a nie opis samego problemu.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22
Zobacz pozostałe 8 komentarzy
stivens
I to najlepiej kilka
stivens
Funkcja celu jest strategia wzgledem ewolucji, nigdy odwrotnie bo to jest parametr
stivens
Cos co przyjmuje jako argument funkcje celu i jakies parametry typu liczba iteracji, prawdopodobienstwo mutacji itd. nie jest abstrakcja a implementacja
stivens
To tak jakbys mowil, ze nie mozna napisac implementacji funkcji list::join jesli ktos Ci nie poda wczesniej dwoch instancji listy ;)
stivens
  • Rejestracja:ponad 8 lat
  • Ostatnio:około 5 godzin
0

@MarekR22: albo moze inaczej to powiem

Kopiuj
def SGA[A](
  crossoverOperator: (DenseVector[A], DenseVector[A]) => (DenseVector[A], DenseVector[A]),
  mutationOperator: DenseVector[A] => DenseVector[A],
  objectiveFunction: DenseVector[A] => Double,
  initialPopulation: DenseMatrix[A],
  populationSize: Int = 500,
  numberOfOffspring: Int = 500,
  crossoverProbability: Double = 0.95,
  mutationProbability: Double = 0.25,
  iterations: Int = 500,
  log: Boolean = true
)

Tutaj jest sygnatura jakiejs mojej implementacji SGA.
Funkcja celu, operator mutacji itd. to tylko parametry. Nie sa one krytyczne do implementacji samego SGA.

EDIT: oczywiscie do testowania juz sa potrzebne


λλλ
edytowany 7x, ostatnio: stivens
AL
  • Rejestracja:ponad 4 lata
  • Ostatnio:około 4 lata
  • Postów:3
0

Dobrze, czyli chodzi o jakiegoś osobnika docelowego, czyli np. const std::string cel = "2 4 24 2 8 65 43"; ale dalej nie wiem jak dzielić elementy vektora w losowych miejscach.

stivens
  • Rejestracja:ponad 8 lat
  • Ostatnio:około 5 godzin
1

Tylko ze Ty masz problem z podstawami programowania a nie z SGA.

Trzeba wylosowac miejsce ciecia i przekopiowac od jednego rodzica i od drugiego.


λλλ
edytowany 1x, ostatnio: stivens
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
0

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)