Un algoritm pentru construirea unui set Pareto, metode numerice pentru construirea unui set Pareto, o descriere

Metode numerice pentru construirea setului Pareto

Problema de alocare a tuturor pixeli efectivi, în forma sa generală, nu a fost încă rezolvată, dar a dezvoltat destul de multe metode diferite pentru a găsi puncte eficiente pentru problemele cu două criteriu și liniare multicriteriale [4].







Luați în considerare cel mai simplu caz (două criterii). Avem problema:

La fiecare punct al

a pus în corespondență un anumit punct în planul criteriilor. Relațiile (2.2) determină maparea setului.

Setul este numit setul de atingere. Setul Pareto este doar o parte din limita setului de accesibilitate.

Construcția aproximativă a setului Pareto reduce la o soluție secvențială a problemelor programării matematice. Să descriem una dintre schemele posibile de calcul.

Reparăm câteva valori dorite ale criteriilor și:

Valorile lui C1 și C2 ar trebui alese astfel încât să facă parte din setul de realizabilitate. Acum rezolvăm două probleme de optimizare:

După rezolvarea acestor probleme, definim punctele a și b (figura 2.1). Trecând printr-o linie dreaptă 1, obținem cea mai simplă aproximare a setului Pareto. Pentru a rafina aproximarea, rezolvăm următoarele probleme:

Mai găsim încă două puncte - c și d. aparținând acestui set. Valorile lui C3 și C4 din nou trebuie să aparțină setului de atingere.







Prin punctele a, c, d și b tragem o linie poligonală 2. care va fi următoarea aproximare. Foarte des, astfel de informații despre structura setului Pareto sunt deja suficiente pentru a rezolva problemele practice.

Dacă setul Pareto convex, creșterea numărului de puncte, care sunt determinate așa cum este descris, vom construi un poliedru aproximând un set, cu orice grad de precizie. Cu toate acestea, practica oferă exemple de seturi Pareto care nu sunt convexe. Apoi, problema apropierii lor este foarte complicată.

Un algoritm pentru construirea unui set Pareto, metode numerice pentru construirea unui set Pareto, o descriere

Astfel, prin calcularea setului Pareto, este posibil să se reducă semnificativ numărul. Astfel, se propune înlocuirea problemei originale cu problema optimizării discrete pe grafic. În același timp, traseul optim din grafic va corespunde traseului dorit.

Descrierea programului

Programul de calcul al setului Pareto este scris în C ++. În fișierul de date. txt stochează datele originale despre pixeli: numărul secvenței de pixeli, valorile de risc și valorile valorilor. Numărul de pixeli 23. Elementele setului Pareto se disting prin definiția setului Pareto.

La calcularea setului Pareto, programul enumeră toate soluțiile posibile.

Ca rezultat al programului, nu mai mult de n comparații ale soluțiilor au loc, unde n este numărul de pixeli. Datele sunt organizate sub forma unei liste. Dacă se obține o decizie dominantă prin comparație, o ștergem din listă și nu participăm la comparație, ceea ce duce la o reducere a numărului de operațiuni.







Articole similare

Trimiteți-le prietenilor: