//Algoritmi za preiskovanje prostora stanj
public class Search {
final int TIMEUP_DEFAULT = 7 ; // dovoljen cas iskanja
public int allowedTime ;
boolean isTimeUp ;
Timer timer ;
final int PQ_LEN_DEFAULT = 10000 ;
public int allowedPQlen ;
public Search() {
allowedTime = TIMEUP_DEFAULT ;
allowedPQlen = PQ_LEN_DEFAULT ;
}
public SearchState breadthFirstSearch(SearchState sz) throws Exception {
SearchState sBest, // trenutno najboljse stanje
s, // trenutno obravnavano stanje
snext ;// naslednik trenutno obravnavanega stanja
Queue open = new QueueLinked() ; // vrsta stanj z nepregledanimi nasledniki
List successors ; // seznam naslednikov trenutno obravnavanega stanja
isTimeUp = false ;
timer = new Timer() ;
timer.schedule(new WaitingTask(), allowedTime*1000);
sBest = sz ;
open.makenull() ;
open.enqueue(sz) ;
while (! open.empty() && !isTimeUp) {
s = (SearchState)open.front() ;
open.dequeue();
successors = s.next() ;
for (Object iter= successors.first() ; !successors.overEnd(iter) ; iter=successors.next(iter)) {
snext = (SearchState)successors.retrieve(iter);
open.enqueue(snext);
if (snext.q() > sBest.q())
sBest = snext ;
}
}
if (!isTimeUp)
timer.cancel();
return sBest ;
}
class WaitingTask extends TimerTask {
public void run() {
isTimeUp = true ;
System.out.println("Timeout. Terminating search!") ;
timer.cancel(); // koncaj cakanje
}
}
public SearchState depthFirstSearch(SearchState sz, int maxDepth) {
// sz - zacetno oz.trenutno obravnavano stanje
SearchState sBest, // trenutno najboljse stanje
snext, // naslednik trenutno obravnavanega stanja
bestNext; // najboljsi naslednik trenutno obravnavanega stanja
List successors; // seznam naslednikov trenutno obravnavanega stanja
if (maxDepth == 0)
return sz;
else {
sBest = sz ;
successors = sz.next() ;
for (Object iter= successors.first() ; !successors.overEnd(iter) ; iter=successors.next(iter)) {
snext = (SearchState)successors.retrieve(iter);
bestNext = depthFirstSearch(snext, maxDepth -1) ;
if (bestNext.q() > sBest.q())
sBest = bestNext ;
}
return sBest ;
}
}
public SearchState iterativeDeepening(SearchState sz) {
// sz - zacetno oz.trenutno obravnavano stanje
SearchState sBest, // trenutno najboljse stanje
bestIter; // najboljse stanje ene iteracije
int depth ; // trenutna globina iteracije
isTimeUp = false ;
timer = new Timer() ;
timer.schedule(new WaitingTask(), allowedTime*1000);
sBest = sz ;
depth = 1 ;
while (!isTimeUp) {
bestIter = depthFirstSearch(sz, depth) ;
if (bestIter.q() > sBest.q())
sBest = bestIter ;
depth++ ;
}
return sBest ;
}
public SearchState limitedBreadthFirstSearch(SearchState sz) throws Exception {
SearchState sBest, // trenutno najboljse stanje
s, // trenutno obravnavano stanje
snext ;// naslednik trenutno obravnavanega stanja
Queue open = new QueueLinked() ; // vrsta stanj z nepregledanimi nasledniki
List successors ; // seznam naslednikov trenutno obravnavanega stanja
isTimeUp = false ;
timer = new Timer() ;
timer.schedule(new WaitingTask(), allowedTime*1000);
sBest = sz ;
open.makenull() ;
open.enqueue(sz) ;
while (! open.empty() && !isTimeUp) {
s = (SearchState)open.front() ;
open.dequeue();
if (s.max() > sBest.q()) {
successors = s.next();
for (Object iter = successors.first(); !successors.overEnd(iter);
iter = successors.next(iter)) {
snext = (SearchState) successors.retrieve(iter);
open.enqueue(snext);
if (snext.q() > sBest.q())
sBest = snext;
}
}
}
if (!isTimeUp)
timer.cancel();
return sBest ;
}
public SearchState limitedDepthFirstSearch(SearchState sz) {
best_ldfs = sz ;
limitedDFS(sz) ;
return best_ldfs ;
}
SearchState best_ldfs ;
public void limitedDFS(SearchState sz) {
// sz - zacetno oz.trenutno obravnavano stanje
// best_ldfs - trenutno najboljse stanje
SearchState snext; // naslednik trenutno obravnavanega stanja
List successors; // seznam naslednikov trenutno obravnavanega stanja
if (sz.q() > best_ldfs.q()) // smo nasli boljse stanje
best_ldfs = sz;
if (sz.max() > best_ldfs.q()) { // ne zavrzimo naslednjikov
successors = sz.next();
for (Object iter = successors.first(); !successors.overEnd(iter);
iter = successors.next(iter)) {
snext = (SearchState) successors.retrieve(iter);
limitedDFS(snext);
}
}
}
public SearchState bestFirstSearch(SearchState sz) {
SearchState sBest, // trenutno najboljse stanje
s, // trenutno obravnavano stanje
snext ;// naslednik trenutno obravnavanega stanja
PriorityQueue open = new Heap(allowedPQlen) ; // prioritetna vrsta stanj z
// nepregledanimi nasledniki, urejena po kvaliteti
List successors ; // seznam naslednikov trenutno obravnavanega stanja
isTimeUp = false ;
timer = new Timer() ;
timer.schedule(new WaitingTask(), allowedTime*1000);
sBest = sz ;
open.makenull() ;
open.insert((Comparable)sz) ; // kljuc je definiran z max()
while (! open.empty() && !isTimeUp) {
s = (SearchState)open.deleteMin() ;
if (s.max() < sBest.q())
open.makenull() ;
else {
successors = s.next();
for (Object iter = successors.first(); !successors.overEnd(iter); iter = successors.next(iter)) {
snext = (SearchState) successors.retrieve(iter);
if (snext.max() > sBest.q()) {
open.insert( (Comparable) snext);
if (snext.q() > sBest.q())
sBest = snext ;
}
}
}
}
if (!isTimeUp)
timer.cancel();
return sBest ;
}
public SearchState greedySearch(SearchState sz) {
// sz - zacetno oz.trenutno obravnavano stanje
SearchState s, // trenutno obravnavano stanje
snext, // naslednik trenutno obravnavanega stanja
sMax; // najboljsi naslednik trenutno obravnavanega stanja
List successors; // seznam naslednikov trenutno obravnavanega stanja
double maxVal ;
s = sz ;
do {
successors = s.next() ;
sMax = null ;
maxVal = - Double.MAX_VALUE ;
for (Object iter= successors.first() ; !successors.overEnd(iter) ; iter=successors.next(iter)) {
snext = (SearchState)successors.retrieve(iter);
if (snext.max() > maxVal) {
sMax = snext ;
maxVal = snext.max() ;
}
}
if (sMax != null)
s = sMax ;
} while (sMax != null) ;
return s ;
}
public void insertToBeam(ListArray beam, SearchState s) {
int pos;
for (pos= ((Integer)beam.last()).intValue(); pos >=0 ; pos--)
if ( ( (SearchState) beam.retrieve(pos)).max() >= s.max())
break ;
if (((Integer)beam.last()).intValue()+1 < beam.length()) { // ali je se kaj prostora
beam.insert(s, new Integer(pos+1)); // vstavimo
}
else if (pos < ((Integer)beam.last()).intValue()) { // samo nekam na sredino
beam.delete(beam.last()) ; // zbrisemo zadnjega
beam.insert(s, new Integer(pos+1)); // vstavimo
}
}
public SearchState beamSearch(SearchState sz, int m) {
// sz - zacetno oz.trenutno obravnavano stanje
SearchState s, // trenutno obravnavano stanje
snext, // naslednik trenutno obravnavanega stanja
sBest ; // najboljse stanje
Set successors = new SetLinked() ; // mnozica naslednikov trenutno obravnavanih stanj
ListArray beam = new ListArray(m), // seznam trenutno obravnavanih stanj
newBeam = new ListArray(m) ;// nov seznam obravnavanih stanj
SetLinked nextSet ;
Object bi, si ; // iteratorja po mnozicah
sBest = sz ;
beam.insert(sz);
do {
successors.makenull();
for (bi = beam.first() ; !beam.overEnd(bi) ; bi=beam.next(bi)) {
s = (SearchState) beam.retrieve(bi);
nextSet = new SetLinked((ListLinked) s.next()) ;
successors.union(nextSet);
}
newBeam.makenull();
for (si = successors.first() ; !successors.overEnd(si) ; si=successors.next(si)) {
snext = (SearchState) successors.retrieve(si) ;
insertToBeam(newBeam, snext);
if (snext.q() > sBest.q())
sBest = snext ;
}
beam = newBeam ;
} while (! successors.empty()) ;
return sBest ;
}
public SearchState simulatedAnnealing(SolutionSearchState s, double tMax, double lambda, double tMin) {
// s - trenutno stanje
double t ; // trenutna temperatura
SolutionSearchState snext ; // naslednik trenutnega stanja
List successors ; // seznam naslednikov
s.setRandom() ;
t = tMax ;
do {
successors = s.next() ;
snext = (SolutionSearchState) successors.retrieve((int)(Math.random()*successors.len())) ; // nakljucni naslednjik
if (Math.random() < Math.exp((snext.q() - s.q())/t))
s = snext ;
t *= lambda ;
} while (t > tMin) ;
// lokalna optimizacija
SolutionSearchState sMax ; // najboljsi naslednjik trenutnega stanja
double maxQ ;
do {
successors = s.next() ;
sMax = null ;
maxQ = -Double.MAX_VALUE ;
for (Object iter= successors.first() ; !successors.overEnd(iter) ; iter=successors.next(iter)) {
snext = (SolutionSearchState)successors.retrieve(iter);
if (snext.q() > maxQ) {
sMax = snext ;
maxQ = snext.q() ;
}
}
if (sMax != null && sMax.q() > s.q())
s = sMax ;
} while (s==sMax) ; // dokler so izboljsave
return s ;
}
public SearchState markovianNeuralNetworks(SolutionSearchState s, double tMax, double lambda, double tMin) {
// s - trenutno stanje
double q,r,sum ; // metanje kocke na intervalu [0,1)
double t ; // trenutna temperatura
SolutionSearchState snext ; // naslednik trenutnega stanja
List successors ; // seznam naslednikov
List betterSucc = new ListLinked() ;
Object iter ; // kazalec na successors
s.setRandom() ;
t = tMax ;
do {
successors = s.next() ;
betterSucc.makenull() ;
for (iter= successors.first() ; !successors.overEnd(iter) ; iter=successors.next(iter)) {
snext = (SolutionSearchState)successors.retrieve(iter);
if (snext.q() > s.q())
betterSucc.insert(snext) ;
}
if (betterSucc.empty()) {
betterSucc = successors ;
betterSucc.insert(s);
}
r = Math.random() ; // met kocke
q = 0.0 ;
// normalizacija verjetnosti
sum = 0.0 ;
for (iter= betterSucc.first() ; !betterSucc.overEnd(iter) ; iter=betterSucc.next(iter)) {
snext = (SolutionSearchState) betterSucc.retrieve(iter);
sum += Math.exp( (snext.q() - s.q()) / t);
}
iter = betterSucc.first() ;
while (q < r) { // iskanje izbranega naslednika
snext = (SolutionSearchState)betterSucc.retrieve(iter) ;
q = q + Math.exp((snext.q() - s.q())/t)/sum ;
if ( q >= r)
s = snext ;
else
iter = betterSucc.next(iter) ;
}
t *= lambda ;
} while (t > tMin) ;
// lokalna optimizacija
SolutionSearchState sMax ; // najboljsi naslednjik trenutnega stanja
double maxQ ;
do {
successors = s.next() ;
sMax = null ;
maxQ = -Double.MAX_VALUE ;
for (iter= successors.first() ; !successors.overEnd(iter) ; iter=successors.next(iter)) {
snext = (SolutionSearchState)successors.retrieve(iter);
if (snext.q() > maxQ) {
sMax = snext ;
maxQ = snext.q() ;
}
}
if (sMax != null && sMax.q() > s.q())
s = sMax ;
} while (s==sMax) ; // dokler so izboljsave
return s ;
}
public SearchState geneticSearch(GeneticProblem p, int g, int n, double pc, double pm) {
// g = stevilo generacij
// n = velikost populacije
// pc = verjetnost krizanja
// pm = verjetnost mutacije
SolutionSearchState s[] = new SolutionSearchState[n]; // trenutna populacija
SolutionSearchState snext[] = new SolutionSearchState[n]; // naslednja populacija
SolutionSearchState c1, c2 ; // rezultata krizanja
double r, q, sum ; // metanje kocke na intervalu [0, 1)
int i,j,k,u,i1,i2 ;
// zacetna populacija
for (i=0 ; i < n ; i++) {
s[i] = p.randomState();
}
SolutionSearchState sBest ;
sBest = s[0] ;
for (u=1 ; u < n ; u++)
if (s[u].q() > sBest.q())
sBest = s[u] ;
for (j=0; j < g ; j++) { // g generacij
// reprodukcija
// izracun normalizacijske vrednosti
sum = 0.0;
for (k=0 ; k < n ; k++)
sum += s[k].q() ;
for (i=0 ; i < n ; i++) {
k=-1 ;
r = Math.random();
q = 0.0;
while (q < r) { // iskanje izbranega prednika
k++;
q += s[k].q() / sum;
}
snext[i] = s[k] ;
} // for i
s = (SolutionSearchState[]) snext.clone() ; // nova populacija
// krizanje: na zacetku je nova populacija enaka trenutni
for (k=0 ; k < pc * n ; k++) {
i1 = (int)(n*Math.random()) ;
i2 = (int)(n*Math.random()) ;
c1 = p.newState() ;
c2 = p.newState() ;
p.crossover(s[i1], s[i2], c1, c2) ;
snext[i1] = c1 ;
snext[i2] = c2 ;
}
s = (SolutionSearchState[]) snext.clone() ; // samo nekateri v snext so se spremenili s krizanjem
for (u=0 ; u < n ; u++)
if (s[u].q() > sBest.q())
sBest = s[u] ;
// mutacija
for (i=0 ; i < n ; i++)
p.mutation(s[i], pm) ;
for (u=0 ; u < n ; u++)
if (s[u].q() > sBest.q())
sBest = s[u] ;
}
return sBest ;
}
public static void main(String[] args) throws Exception {
Search search = new Search() ;
int noCities = 8 ;
search.allowedTime = 7;
TSPgeneticProblem p = new TSPgeneticProblem(noCities) ;
System.out.println("Random TSP problem with "+noCities+" cities");
p.printOut() ;
TSPstate sz = new TSPstate(p) ;
sz.init(0); // zacnemo recimo v mestu 0
// v sirino
System.out.println("Iskanje v irino") ;
TSPstate brfs = (TSPstate) search.breadthFirstSearch(sz) ;
System.out.println("Maksimalna reitev "+brfs.q()+": ") ;
brfs.printOut();
System.out.println() ;
// v globino
System.out.println("Iskanje v globino") ;
TSPstate dfs = (TSPstate) search.depthFirstSearch(sz, noCities+1) ;
System.out.println("Maksimalna reitev "+dfs.q()+": ") ;
dfs.printOut();
System.out.println() ;
// iterativno poglabljanje
System.out.println("Iterativno poglabjanje") ;
TSPstate id = (TSPstate) search.iterativeDeepening(sz) ;
System.out.println("Maksimalna reitev "+id.q()+": ") ;
id.printOut();
System.out.println() ;
// omejeno v sirino
System.out.println("Omejeno iskanje v irino") ;
TSPstate lbfs = (TSPstate) search.limitedBreadthFirstSearch(sz) ;
System.out.println("Maksimalna reitev "+lbfs.q()+": ") ;
lbfs.printOut();
System.out.println() ;
// omejeno v sirino
System.out.println("Omejeno iskanje v globino") ;
TSPstate ldfs = (TSPstate) search.limitedDepthFirstSearch(sz) ;
System.out.println("Maksimalna reitev "+ldfs.q()+": ") ;
ldfs.printOut();
System.out.println() ;
// najprej najboljsi
search.allowedPQlen = 1000000 ;
System.out.println("Iskanje najprej najbolji") ;
TSPstate bfs = (TSPstate) search.bestFirstSearch(sz) ;
System.out.println("Maksimalna reitev "+bfs.q()+": ") ;
bfs.printOut();
System.out.println() ;
// pozresno
System.out.println("Poreno iskanje") ;
TSPstate gs = (TSPstate) search.greedySearch(sz) ;
System.out.println("Maksimalna reitev "+gs.q()+": ") ;
gs.printOut();
System.out.println() ;
// v snopu
System.out.println("Iskanje v snopu") ;
TSPstate beams = (TSPstate) search.beamSearch(sz, 10) ;
System.out.println("Maksimalna reitev "+beams.q()+": ") ;
beams.printOut();
System.out.println() ;
// simulirano ohlajanje
System.out.println("Simulirano ohlajanje") ;
TSPsolutionState ss = new TSPsolutionState(p) ;
ss.setRandom() ; // zacnemo z nakljucno konfiguracijo
int[] rw = (int[])ss.walk.clone() ;
System.out.println("Zacetna konfiguracija "+ss.q()+": ") ;
ss.printOut();
System.out.println() ;
TSPstate sa = (TSPstate)search.simulatedAnnealing(ss, 1000, 0.8, 10) ;
System.out.println("Maksimalna reitev "+sa.q()+": ") ;
sa.printOut();
System.out.println() ;
// markovske nevronske mreze
System.out.println("Markovske nevronske mree") ;
ss.walk = (int[])rw.clone() ;
System.out.println("Zacetna konfiguracija "+ss.q()+": ") ;
ss.printOut();
System.out.println() ;
TSPstate mnn = (TSPstate)search.markovianNeuralNetworks(ss, 1000, 0.8, 10) ;
System.out.println("Maksimalna reitev "+mnn.q()+": ") ;
mnn.printOut();
System.out.println() ;
// genetski algoritem
System.out.println("Genetski algoritem") ;
TSPstate ga = (TSPstate)search.geneticSearch(p, 100, 100, 0.4, 0.05) ;
System.out.println("Maksimalna reitev "+ga.q()+": ") ;
ga.printOut();
System.out.println() ;
}
}
