30 #define _CRT_SECURE_NO_DEPRECATE
58 delete[] chain->
label;
64 : nbLabelledLayers( 0 )
69 , labelPositionCost( NULL )
73 , inactiveCost( NULL )
86 candidates_subsol = NULL;
101 delete[] featStartId;
105 qDeleteAll( mLabelPositions );
106 mLabelPositions.clear();
109 delete[] inactiveCost;
112 delete candidates_sol;
114 if ( candidates_subsol )
116 delete candidates_subsol;
130 return ((
SubPart* ) l )->borderSize < ((
SubPart* ) r )->borderSize;
135 return ((
SubPart* ) l )->borderSize > ((
SubPart* ) r )->borderSize;
140 return ((
Ft* ) l )->inactiveCost < ((
Ft* ) r )->inactiveCost;
145 return ((
Ft* ) l )->nbOverlap > ((
Ft* ) r )->nbOverlap;
161 bool *ok =
new bool[nblp];
164 for ( i = 0; i < nblp; i++ )
175 for ( i = 0; i < nbft; i++ )
178 for ( j = 0; j < featNbLp[i]; j++ )
180 if ( !ok[featStartId[i] + j] )
182 if ( mLabelPositions.at( featStartId[i] + j )->getNumOverlaps() == 0 )
185 ok[featStartId[i] + j] =
true;
188 counter += featNbLp[i] - j - 1;
190 for ( k = j + 1; k < featNbLp[i]; k++ )
193 lpid = featStartId[i] + k;
195 lp2 = mLabelPositions.at( lpid );
213 this->nblp -= counter;
215 std::cout <<
"problem reduce to " << nblp <<
" candidates which makes " << nbOverlap <<
" overlaps" << std::endl;
232 sol->
s =
new int[nbft];
234 for ( i = 0; i < nbft; i++ )
269 context->
list = list;
308 std::cout <<
"Init solution FALP" << std::endl;
324 context->
list = list;
328 for ( i = 0; i < nbft; i++ )
329 for ( j = 0; j < featNbLp[i]; j++ )
331 label = featStartId[i] + j;
334 list->
insert( label, (
double ) mLabelPositions.at( label )->getNumOverlaps() );
344 if (
pal->isCancelled() )
354 lp = mLabelPositions.at( label );
356 if ( lp->
getId() != label )
358 std::cout <<
"Error: " << lp->
getId() <<
" <--> " << label << std::endl;
362 sol->
s[probFeatId] = label;
365 std::cout <<
"sol->s[" << lp->
probFeat <<
"] :" << label << std::endl;
368 for ( i = featStartId[probFeatId]; i < featStartId[probFeatId] + featNbLp[probFeatId]; i++ )
370 ignoreLabel( mLabelPositions.at( i ), list, candidates );
377 candidates->Search( amin, amax,
falpCallback1, (
void* ) context );
378 candidates_sol->Insert( amin, amax, lp );
393 for ( i = 0; i < nbft; i++ )
395 if ( sol->
s[i] == -1 )
398 start_p = featStartId[i];
399 for ( p = 0; p < featNbLp[i]; p++ )
401 lp = mLabelPositions.at( start_p + p );
415 sol->
s[i] = retainedLabel->
getId();
435 bool *ok =
new bool[nbft];
437 int r =
pal->popmusic_r;
448 clock_t start_time = clock();
449 clock_t create_part_time;
450 clock_t init_sol_time;
457 int subPartTotalSize = 0;
460 labelPositionCost =
new double[all_nblp];
461 nbOlap =
new int[all_nblp];
463 featWrap =
new int[nbft];
464 memset( featWrap, -1,
sizeof(
int ) *nbft );
467 int *isIn =
new int[nbft];
469 memset( isIn, 0,
sizeof(
int ) *nbft );
472 for ( i = 0; i < nbft; i++ )
474 parts[i] =
subPart( r, i, isIn );
476 subPartTotalSize += parts[i]->
subSize;
485 create_part_time = clock();
486 std::cout <<
" SubPart (averagesize: " << subPartTotalSize / nbft <<
") creation: " << ( double )( create_part_time - start_time ) / ( double ) CLOCKS_PER_SEC << std::endl;
492 init_sol_time = clock();
493 std::cout <<
" Compute initial solution: " << ( double )( init_sol_time - create_part_time ) / ( double ) CLOCKS_PER_SEC;
499 std::cerr <<
"\t" << sol->
cost <<
"\t" << nbActive <<
"\t" << ( double ) nbActive / (
double ) nbft;
500 std::cout <<
" (solution cost: " << sol->
cost <<
", nbDisplayed: " << nbActive <<
"(" << ( double ) nbActive / (
double ) nbft <<
"%)" << std::endl;
511 for ( i = ( seed + 1 ) % nbft; ok[i] && i !=
seed; i = ( i + 1 ) % nbft )
514 if ( i == seed && ok[seed] )
522 current = parts[
seed];
526 candidates_subsol->RemoveAll();
528 for ( i = 0; i < current->
subSize; i++ )
530 current->
sol[i] = sol->
s[current->
sub[i]];
531 if ( current->
sol[i] != -1 )
533 mLabelPositions.at( current->
sol[i] )->insertIntoIndex( candidates_subsol );
537 switch ( searchMethod )
554 std::cerr <<
"Unknown search method..." << std::endl;
567 std::cout <<
"Update solution from subpart, current cost:" << std::endl;
569 std::cout <<
"Delta > EPSILON: update solution" << std::endl;
570 std::cout <<
"after modif cost:" << std::endl;
575 ok[current->
sub[i]] =
false;
578 for ( i = current->
borderSize; i < current->subSize; i++ )
581 if ( sol->
s[current->
sub[i]] != -1 )
583 mLabelPositions.at( sol->
s[current->
sub[i]] )->removeFromIndex( candidates_sol );
586 sol->
s[current->
sub[i]] = current->
sol[i];
588 if ( current->
sol[i] != -1 )
590 mLabelPositions.at( current->
sol[i] )->insertIntoIndex( candidates_sol );
593 ok[current->
sub[i]] =
false;
599 std::cout <<
"subpart not improved" << std::endl;
607 search_time = clock();
608 std::cout <<
" Improved solution: " << ( double )( search_time - start_time ) / ( double ) CLOCKS_PER_SEC <<
" (solution cost: " << sol->
cost <<
", nbDisplayed: " << nbActive <<
" (" << (
double ) nbActive / ( double ) nbft <<
")" << std::endl;
611 std::cerr <<
"\t" << subPartTotalSize;
614 std::cerr <<
"\tpop_tabu\t";
616 std::cerr <<
"\tpop_tabu_chain\t";
618 std::cerr <<
"\tpop_chain\t";
620 std::cerr << r <<
"\t" << popit <<
"\t" << ( create_part_time - start_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << ( init_sol_time - create_part_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << ( search_time - init_sol_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << ( search_time - start_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << sol->
cost <<
"\t" << nbActive <<
"\t" << ( double ) nbActive / (
double ) nbft;
624 delete[] labelPositionCost;
627 for ( i = 0; i < nbft; i++ )
629 delete[] parts[i]->
sub;
630 delete[] parts[i]->
sol;
684 context.
queue = queue;
687 queue->
append( featseed );
692 while ( ri->
size() < r && queue->
size() > 0 )
697 featS = featStartId[id];
700 for ( i = featS; i < featS + p; i++ )
702 lp = mLabelPositions.at( i );
718 while ( queue->
size() > 0 )
725 while ( ri->
size() > 0 )
742 subPart->
seed = featseed;
753 context.
nbOv = nbOverlap;
754 context.
cost = &cost;
764 lp = mLabelPositions.at( label_id );
775 cost = inactiveCost[part->
sub[feat_id]];
791 for ( i = 0; i < part->
subSize; i++ )
813 return ((
Triple* ) tl )->cost < ((
Triple* ) tr )->cost;
818 return ((
Triple* ) tl )->cost > ((
Triple* ) tr )->cost;
824 double candidateBaseFactor,
double *candidateFactor,
825 int minCandidateListSize,
double reductionFactor,
826 int minTabuTSize,
double tabuFactor,
int *tenure,
int n )
829 if ( *candidateFactor > candidateBaseFactor )
830 *candidateFactor /= reductionFactor;
832 if ( iteration % m == 0 )
834 *tenure = minTabuTSize + ( int )( tabuFactor * nbOverlap );
835 *candidateListSize = minCandidateListSize + ( int )( *candidateFactor * nbOverlap );
837 if ( *candidateListSize > n )
838 *candidateListSize = n;
845 double *candidateFactor,
int minCandidateListSize,
double growingFactor,
int n )
848 candidateBaseFactor += 0;
850 if ( *candidateListSize < n )
851 *candidateFactor = *candidateFactor * growingFactor;
852 *candidateListSize = minCandidateListSize + ( int )( *candidateFactor * nbOverlap );
854 if ( *candidateListSize > n )
855 *candidateListSize = n;
887 if ( feat_id >= 0 && ctx->
sol[feat_id] == lp->
getId() )
889 if (( feat_id2 = feat_id - ctx->
borderSize ) >= 0 )
905 std::cout <<
"Subpart: Tabu Search" << std::endl;
911 int *sub = part->
sub;
912 int *sol = part->
sol;
917 int * best_sol =
new int[subSize];
923 int *tabu_list =
new int[probSize];
953 int minTabuTSize = 9;
954 double tabuFactor = 0.5;
956 int minCandidateListSize = 18;
958 double candidateBaseFactor = 0.73;
960 double growingFactor = 15;
961 double reductionFactor = 1.3;
963 int candidateListSize = minCandidateListSize;
964 double candidateFactor = candidateBaseFactor;
970 max_it = probSize *
pal->tabuMaxIt;
971 itwImp = probSize *
pal->tabuMinIt;
979 for ( i = 0; i < subSize; i++ )
980 featWrap[sub[i]] = i;
982 for ( i = 0; i < subSize; i++ )
984 j = featStartId[sub[i]];
985 for ( lp = 0; lp < featNbLp[sub[i]]; lp++ )
995 first_lp = ( displayAll ? 0 : -1 );
996 for ( i = 0; i < probSize; i++ )
1001 candidateList[i] =
new Triple();
1002 candidateList[i]->
feat_id = i + borderSize;
1003 candidateList[i]->
label_id = sol[i+borderSize];
1005 candidateListUnsorted[i] = candidateList[i];
1007 if ( sol[i+borderSize] >= 0 )
1009 j = sol[i+borderSize];
1010 candidateList[i]->
cost = labelPositionCost[j];
1011 candidateList[i]->
nbOverlap = nbOlap[j];
1015 candidateList[i]->
cost = inactiveCost[sub[i+borderSize]];
1022 for ( i = 0; i < subSize; i++ )
1026 cur_cost += inactiveCost[sub[i]];
1030 nbOverlap += nbOlap[sol[i]];
1031 cur_cost += labelPositionCost[sol[i]];
1037 best_cost = cur_cost;
1038 initial_cost = cur_cost;
1039 memcpy( best_sol, sol,
sizeof(
int ) *( subSize ) );
1044 while ( it < stop_it && best_cost >=
EPSILON )
1047 std::cout <<
" ITERATION : " << it <<
" stop: " << stop_it << std::endl;
1049 actualizeTabuCandidateList( m, it, nbOverlap, &candidateListSize, candidateBaseFactor, &candidateFactor, minCandidateListSize, reductionFactor, minTabuTSize, tabuFactor, &tenure, probSize );
1050 delta_min = DBL_MAX;
1056 for ( i = 0; i < candidateListSize; i++ )
1058 feat_id = candidateList[i]->
feat_id;
1059 feat_sub_id = sub[feat_id];
1060 label_id = candidateList[i]->
label_id;
1062 int oldPos = ( label_id < 0 ? -1 : label_id - featStartId[feat_sub_id] );
1065 p = featNbLp[feat_sub_id];
1069 for ( j = first_lp; j < p; j++ )
1074 if ( sol[feat_id] < 0 )
1076 delta = -inactiveCost[feat_sub_id];
1080 delta = -labelPositionCost[sol[feat_id]];
1081 delta -= nbOlap[sol[feat_id]] * ( inactiveCost[feat_sub_id] + mLabelPositions.at( label_id )->cost() );
1086 delta += labelPositionCost[featStartId[feat_sub_id] + j];
1087 delta += nbOlap[featStartId[feat_sub_id] + j] * ( inactiveCost[feat_sub_id] + mLabelPositions.at( featStartId[feat_sub_id] + j )->cost() );
1091 delta += inactiveCost[feat_sub_id];
1095 std::cout <<
" test moving " << oldPos <<
" to " << featStartId[feat_sub_id] + j << std::endl;
1096 std::cout <<
" new pos makes " << nbOlap[featStartId[feat_sub_id] + j] <<
" overlaps" << std::endl;
1097 std::cout <<
" delta is : " << delta << std::endl;
1100 authorized = ( tabu_list[feat_id - borderSize] <= it ) || ( cur_cost + delta < best_cost );
1103 if ( tabu_list[feat_id - borderSize] > it )
1105 std::cout <<
" Move is tabu" << std::endl;
1109 std::cout <<
" Move is ok" << std::endl;
1112 if ( delta < delta_min && authorized )
1115 std::cout <<
" keep move" << std::endl;
1116 std::cout <<
" choosed_feat: " << feat_id << std::endl;
1118 std::cout <<
" choosed_label: " << j << std::endl;
1120 std::cout <<
" choosed_label: " << featStartId[feat_sub_id] + j << std::endl;
1122 std::cout <<
" delta: " << delta << std::endl;
1125 choosed_feat = feat_id;
1130 choosed_label = featStartId[feat_sub_id] + j;
1136 else if ( !authorized )
1138 std::cout <<
" tabu" << std::endl;
1142 std::cout <<
" no good enough" << std::endl;
1150 if ( choosed_feat >= 0 )
1153 std::cout <<
" Apply move:" << std::endl;
1154 std::cout <<
" feat: " << choosed_feat << std::endl;
1155 std::cout <<
" label: " << choosed_label << std::endl;
1156 std::cout <<
" delta: " << delta_min << std::endl << std::endl;
1159 int old_label = sol[choosed_feat];
1161 tabu_list[choosed_feat-borderSize] = it + tenure;
1162 sol[choosed_feat] = choosed_label;
1163 candidateList[candidateId]->
label_id = choosed_label;
1165 if ( old_label != -1 )
1166 mLabelPositions.at( old_label )->removeFromIndex( candidates_subsol );
1169 double local_inactive = inactiveCost[sub[choosed_feat]];
1171 if ( choosed_label != -1 )
1173 candidateList[candidateId]->
cost = labelPositionCost[choosed_label];
1174 candidateList[candidateId]->
nbOverlap = nbOlap[choosed_label];
1178 candidateList[candidateId]->
cost = local_inactive;
1179 candidateList[candidateId]->
nbOverlap = 1;
1182 cur_cost += delta_min;
1197 if ( old_label >= 0 )
1199 lp = mLabelPositions.at( old_label );
1209 if ( choosed_label >= 0 )
1211 lp = mLabelPositions.at( choosed_label );
1226 if ( best_cost - cur_cost >
EPSILON )
1228 best_cost = cur_cost;
1229 memcpy( best_sol, sol,
sizeof(
int ) *( subSize ) );
1230 stop_it = it + itwImp;
1231 if ( stop_it > max_it )
1239 &candidateFactor, minCandidateListSize, growingFactor, probSize );
1242 std::cout <<
"cost : " << cur_cost << std::endl;
1245 std::cout <<
"best_cost: " << best_cost << std::endl << std::endl;
1250 memcpy( sol, best_sol,
sizeof(
int ) *( subSize ) );
1252 for ( i = 0; i < subSize; i++ )
1253 featWrap[sub[i]] = -1;
1255 for ( i = 0; i < probSize; i++ )
1256 delete candidateList[i];
1258 delete[] candidateList;
1259 delete[] candidateListUnsorted;
1264 return initial_cost - best_cost;
1292 std::cout <<
"chainCallback" << std::endl;
1293 std::cout <<
" lp from rtree: " << lp << std::endl;
1294 std::cout <<
" lpid from rtree: " << lp->
id << std::endl;
1295 std::cout <<
" lpco from rtree: " << lp->
cost << std::endl;
1296 std::cout <<
" lp from context: " << ctx->
lp << std::endl;
1297 std::cout <<
" lpid from context: " << ctx->
lp->
id << std::endl;
1298 std::cout <<
" lpco from context: " << ctx->
lp->
cost << std::endl;
1299 std::cout <<
" delta_tmp: " << ctx->
delta_tmp << std::endl;
1300 std::cout <<
" *delta_tmp: " << *ctx->
delta_tmp << std::endl;
1301 std::cout <<
" inactiveCost: " << ctx->
inactiveCost << std::endl;
1305 std::cout <<
"ejChCallBack: " << lp->
id <<
"<->" << ctx->
lp->
id << std::endl;
1310 std::cout <<
"ejChCallBack: " << lp->
id <<
"<->" << ctx->
lp->
id << std::endl;
1311 std::cout <<
" Conflictual..." << std::endl;
1326 std::cout <<
" feat: " << feat << std::endl;
1327 std::cout <<
" sol: " << ctx->
tmpsol[feat] <<
"/" << lp->
id << std::endl;
1328 std::cout <<
" border:" << ctx->
borderSize << std::endl;
1330 if ( feat >= 0 && ctx->
tmpsol[feat] == lp->
getId() )
1332 if ( sub && feat < ctx->borderSize )
1335 std::cout <<
" Cannot touch border (throw) !" << std::endl;
1345 if (( *cur )->feat == feat )
1348 std::cout <<
"Cycle into chain (throw) !" << std::endl;
1372 int borderSize = part->borderSize;
1373 int subSize = part->subSize;
1374 int *sub = part->sub;
1375 int *sol = part->sol;
1380 double delta_best = DBL_MAX;
1385 Chain *retainedChain = NULL;
1387 int max_degree =
pal->ejChainDeg;
1394 int *tmpsol =
new int[subSize];
1395 memcpy( tmpsol, sol,
sizeof(
int ) *subSize );
1401 ChainContext context;
1402 context.featWrap = featWrap;
1403 context.borderSize = borderSize;
1404 context.tmpsol = tmpsol;
1405 context.inactiveCost = inactiveCost;
1406 context.feat = NULL;
1407 context.currentChain = currentChain;
1408 context.conflicts = conflicts;
1409 context.delta_tmp = &delta_tmp;
1412 while ( seed != -1 )
1414 subseed = sub[
seed];
1415 seedNbLp = featNbLp[subseed];
1416 delta_min = DBL_MAX;
1418 std::cout <<
"New seed: " << seed <<
"/" << subseed << std::endl;
1424 if ( tmpsol[seed] == -1 )
1425 delta -= inactiveCost[subseed];
1427 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
1430 for ( i = -1; i < seedNbLp; i++ )
1435 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[subseed] != tmpsol[seed] )
1439 lid = featStartId[subseed] + i;
1442 lp = mLabelPositions.at( lid );
1445 lp->getBoundingBox( amin, amax );
1449 if ( conflicts->
size() != 0 )
1450 std::cerr <<
"Conflicts not empty !!" << std::endl;
1453 candidates_subsol->Search( amin, amax,
chainCallback, (
void* ) &context );
1456 std::cout <<
"Conflicts:" << conflicts->
size() << std::endl;
1459 if ( conflicts->
size() == 0 )
1461 if ( !retainedChain || delta + lp->cost() < delta_best )
1464 if ( retainedChain )
1466 delete[] retainedChain->label;
1467 delete[] retainedChain->feat;
1471 retainedChain =
new Chain();
1474 delta_best = delta + lp->cost();
1476 retainedChain->degree = currentChain->
size() + 1;
1477 retainedChain->feat =
new int[retainedChain->degree];
1478 retainedChain->label =
new int[retainedChain->degree];
1482 while ( current != currentChain->
end() )
1485 retainedChain->feat[j] = move->feat;
1486 retainedChain->label[j] = move->new_label;
1490 retainedChain->feat[j] =
seed;
1491 retainedChain->label[j] = lid;
1492 retainedChain->delta = delta + mLabelPositions.at( retainedChain->label[j] )->cost();
1497 else if ( conflicts->
size() == 1 )
1499 if ( delta_tmp < delta_min )
1501 delta_min = delta_tmp;
1502 retainedLabel = lid;
1515 newChain->degree = currentChain->
size() + 1 + conflicts->
size();
1516 newChain->feat =
new int[newChain->degree];
1517 newChain->label =
new int[newChain->degree];
1521 while ( current != currentChain->
end() )
1524 newChain->feat[j] = move->feat;
1525 newChain->label[j] = move->new_label;
1530 newChain->feat[j] =
seed;
1531 newChain->label[j] = lid;
1532 newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
1536 while ( conflicts->
size() > 0 )
1539 newChain->feat[j] = ftid;
1540 newChain->label[j] = -1;
1541 newChain->delta += inactiveCost[sub[ftid]];
1545 if ( newChain->delta < delta_best )
1547 if ( retainedChain )
1550 delta_best = newChain->delta;
1551 retainedChain = newChain;
1561 if ( !retainedChain || delta + inactiveCost[subseed] < delta_best )
1563 if ( retainedChain )
1565 delete[] retainedChain->label;
1566 delete[] retainedChain->feat;
1569 retainedChain =
new Chain();
1571 delta_best = delta + inactiveCost[subseed];
1573 retainedChain->degree = currentChain->
size() + 1;
1574 retainedChain->feat =
new int[retainedChain->degree];
1575 retainedChain->label =
new int[retainedChain->degree];
1579 while ( current != currentChain->
end() )
1582 retainedChain->feat[j] = move->feat;
1583 retainedChain->label[j] = move->new_label;
1587 retainedChain->feat[j] =
seed;
1588 retainedChain->label[j] = -1;
1589 retainedChain->delta = delta + inactiveCost[subseed];
1597 std::cout <<
"catch int " << i << std::endl;
1605 if ( next_seed == -1 )
1609 else if ( currentChain->
size() > max_degree )
1612 std::cout <<
"Max degree reached !! (" << max_degree <<
")" << std::endl;
1620 et->old_label = tmpsol[
seed];
1621 et->new_label = retainedLabel;
1622 currentChain->
append( et );
1624 if ( et->old_label != -1 )
1626 mLabelPositions.at( et->old_label )->removeFromIndex( candidates_subsol );
1629 if ( et->new_label != -1 )
1631 mLabelPositions.at( et->new_label )->insertIntoIndex( candidates_subsol );
1634 tmpsol[
seed] = retainedLabel;
1635 delta += mLabelPositions.at( retainedLabel )->cost();
1640 while ( currentChain->
size() > 0 )
1644 if ( et->new_label != -1 )
1646 mLabelPositions.at( et->new_label )->removeFromIndex( candidates_subsol );
1649 if ( et->old_label != -1 )
1651 mLabelPositions.at( et->old_label )->insertIntoIndex( candidates_subsol );
1656 delete currentChain;
1662 return retainedChain;
1666 inline Chain *Problem::chain(
int seed )
1676 double delta_best = DBL_MAX;
1681 Chain *retainedChain = NULL;
1683 int max_degree =
pal->ejChainDeg;
1690 int *tmpsol =
new int[nbft];
1691 memcpy( tmpsol, sol->s,
sizeof(
int ) *nbft );
1697 ChainContext context;
1698 context.featWrap = NULL;
1699 context.borderSize = 0;
1700 context.tmpsol = tmpsol;
1701 context.inactiveCost = inactiveCost;
1702 context.feat = NULL;
1703 context.currentChain = currentChain;
1704 context.conflicts = conflicts;
1705 context.delta_tmp = &delta_tmp;
1708 while ( seed != -1 )
1710 seedNbLp = featNbLp[
seed];
1711 delta_min = DBL_MAX;
1717 if ( tmpsol[seed] == -1 )
1718 delta -= inactiveCost[
seed];
1720 delta -= mLabelPositions.at( tmpsol[seed] )->cost();
1722 for ( i = -1; i < seedNbLp; i++ )
1727 if ( !( tmpsol[seed] == -1 && i == -1 ) && i + featStartId[seed] != tmpsol[seed] )
1731 lid = featStartId[
seed] + i;
1734 lp = mLabelPositions.at( lid );
1737 lp->getBoundingBox( amin, amax );
1740 if ( conflicts->
size() != 0 )
1741 std::cerr <<
"Conflicts not empty" << std::endl;
1743 candidates_sol->Search( amin, amax,
chainCallback, (
void* ) &context );
1746 if ( conflicts->
size() == 0 )
1748 if ( !retainedChain || delta + lp->cost() < delta_best )
1750 if ( retainedChain )
1752 delete[] retainedChain->label;
1753 delete[] retainedChain->feat;
1757 retainedChain =
new Chain();
1760 delta_best = delta + lp->cost();
1762 retainedChain->degree = currentChain->
size() + 1;
1763 retainedChain->feat =
new int[retainedChain->degree];
1764 retainedChain->label =
new int[retainedChain->degree];
1768 while ( current != currentChain->
end() )
1771 retainedChain->feat[j] = move->feat;
1772 retainedChain->label[j] = move->new_label;
1776 retainedChain->feat[j] =
seed;
1777 retainedChain->label[j] = lid;
1778 retainedChain->delta = delta + lp->cost();
1783 else if ( conflicts->
size() == 1 )
1785 if ( delta_tmp < delta_min )
1787 delta_min = delta_tmp;
1788 retainedLabel = lid;
1801 newChain->degree = currentChain->
size() + 1 + conflicts->
size();
1802 newChain->feat =
new int[newChain->degree];
1803 newChain->label =
new int[newChain->degree];
1808 while ( current != currentChain->
end() )
1811 newChain->feat[j] = move->feat;
1812 newChain->label[j] = move->new_label;
1818 newChain->feat[j] =
seed;
1819 newChain->label[j] = lid;
1820 newChain->delta = delta + mLabelPositions.at( newChain->label[j] )->cost();
1824 while ( conflicts->
size() > 0 )
1827 newChain->feat[j] = ftid;
1828 newChain->label[j] = -1;
1829 newChain->delta += inactiveCost[ftid];
1833 if ( newChain->delta < delta_best )
1835 if ( retainedChain )
1838 delta_best = newChain->delta;
1839 retainedChain = newChain;
1850 if ( !retainedChain || delta + inactiveCost[seed] < delta_best )
1852 if ( retainedChain )
1854 delete[] retainedChain->label;
1855 delete[] retainedChain->feat;
1858 retainedChain =
new Chain();
1860 delta_best = delta + inactiveCost[
seed];
1862 retainedChain->degree = currentChain->
size() + 1;
1863 retainedChain->feat =
new int[retainedChain->degree];
1864 retainedChain->label =
new int[retainedChain->degree];
1868 while ( current != currentChain->
end() )
1871 retainedChain->feat[j] = move->feat;
1872 retainedChain->label[j] = move->new_label;
1876 retainedChain->feat[j] =
seed;
1877 retainedChain->label[j] = -1;
1878 retainedChain->delta = delta + inactiveCost[
seed];
1886 std::cout <<
"catch Cycle in chain" << std::endl;
1894 if ( next_seed == -1 )
1898 else if ( currentChain->
size() > max_degree )
1900 std::cout <<
"Max degree reached !! (" << max_degree <<
")" << std::endl;
1907 et->old_label = tmpsol[
seed];
1908 et->new_label = retainedLabel;
1909 currentChain->
append( et );
1911 if ( et->old_label != -1 )
1913 mLabelPositions.at( et->old_label )->removeFromIndex( candidates_sol );
1916 if ( et->new_label != -1 )
1918 mLabelPositions.at( et->new_label )->insertIntoIndex( candidates_sol );
1922 tmpsol[
seed] = retainedLabel;
1923 delta += mLabelPositions.at( retainedLabel )->cost();
1929 while ( currentChain->
size() > 0 )
1933 if ( et->new_label != -1 )
1935 mLabelPositions.at( et->new_label )->removeFromIndex( candidates_sol );
1938 if ( et->old_label != -1 )
1940 mLabelPositions.at( et->old_label )->insertIntoIndex( candidates_sol );
1945 delete currentChain;
1951 return retainedChain;
1962 int *sub = part->
sub;
1963 int *sol = part->
sol;
1965 int *best_sol =
new int[subSize];
1967 for ( i = 0; i < subSize; i++ )
1969 featWrap[sub[i]] = i;
1970 best_sol[i] = sol[i];
1973 double initial_cost;
1974 double cur_cost = 0;
1975 double best_cost = 0;
1986 int *tabu_list =
new int[subSize];
1988 Chain *current_chain = NULL;
1997 int tenure =
pal->tenure;
1999 for ( i = 0; i < subSize; i++ )
2005 initial_cost = cur_cost;
2006 best_cost = cur_cost;
2010 maxit = probSize *
pal->tabuMaxIt;
2012 itwimp = probSize *
pal->tabuMinIt;
2017 for ( i = 0; i < borderSize; i++ )
2018 tabu_list[i] = maxit;
2020 for ( i = 0; i < probSize; i++ )
2021 tabu_list[i+borderSize] = -1;
2023 while ( it < stop_it )
2025 seed = ( it % probSize ) + borderSize;
2027 current_chain = chain( part, seed );
2028 if ( current_chain )
2033 if ( tabu_list[seed] < it || ( cur_cost + current_chain->
delta ) - best_cost < 0.0 )
2036 for ( i = 0; i < current_chain->
degree; i++ )
2038 fid = current_chain->
feat[i];
2039 lid = current_chain->
label[i];
2041 if ( sol[fid] >= 0 )
2043 mLabelPositions.at( sol[fid] )->removeFromIndex( candidates_subsol );
2047 if ( sol[fid] >= 0 )
2049 mLabelPositions.at( lid )->insertIntoIndex( candidates_subsol );
2052 tabu_list[fid] = it + tenure;
2055 cur_cost += current_chain->
delta;
2057 std::cout <<
"cur->cost: " << cur_cost << std::endl;
2062 if ( best_cost - cur_cost >
EPSILON )
2064 best_cost = cur_cost;
2065 memcpy( best_sol, sol,
sizeof(
int ) *subSize );
2067 stop_it = ( it + itwimp > maxit ? maxit : it + itwimp );
2075 memcpy( sol, best_sol,
sizeof(
int ) *subSize );
2095 for ( i = 0; i < subSize; i++ )
2096 featWrap[sub[i]] = -1;
2102 return initial_cost - best_cost;
2112 int *sub = part->
sub;
2113 int *sol = part->
sol;
2115 int *best_sol =
new int[subSize];
2117 for ( i = 0; i < subSize; i++ )
2119 featWrap[sub[i]] = i;
2122 double initial_cost;
2123 double cur_cost = 0;
2124 double best_cost = 0;
2135 int *tabu_list =
new int[subSize];
2137 Chain *retainedChain = NULL;
2138 Chain *current_chain = NULL;
2147 int tenure =
pal->tenure;
2154 for ( i = 0; i < subSize; i++ )
2160 initial_cost = cur_cost;
2161 best_cost = cur_cost;
2165 maxit = probSize *
pal->tabuMaxIt;
2167 itwimp = probSize *
pal->tabuMinIt;
2171 for ( i = 0; i < borderSize; i++ )
2172 tabu_list[i] = maxit;
2175 for ( i = 0; i < probSize; i++ )
2177 tabu_list[i+borderSize] = -1;
2179 candidates[i] =
new Triple();
2180 candidates[i]->
feat_id = i + borderSize;
2181 candidatesUnsorted[i] = candidates[i];
2183 candidates[i]->
cost = ( sol[i+borderSize] == -1 ? inactiveCost[i+borderSize] : mLabelPositions.at( sol[i+borderSize] )->cost() );
2188 int candidateListSize;
2189 candidateListSize = int (
pal->candListSize * (
double ) probSize + 0.5 );
2191 if ( candidateListSize > probSize )
2192 candidateListSize = probSize;
2196 std::cout << std::endl <<
"Initial solution cost " << cur_cost << std::endl;
2198 std::cout <<
"NbOverlap: " << nbOv << std::endl;
2200 while ( it < stop_it )
2202 retainedChain = NULL;
2205 std::cout << std::endl << std::endl << candidateListSize << std::endl;
2207 for ( itC = 0; itC < candidateListSize; itC++ )
2209 seed = candidates[itC]->
feat_id;
2212 std::cout <<
"new candidates:" << std::endl;
2214 current_chain = chain( part, seed );
2217 std::cout <<
"get chain:" << current_chain << std::endl;
2219 if ( current_chain )
2222 if ( tabu_list[seed] < it || ( cur_cost + current_chain->
delta ) - best_cost < 0.0 )
2224 if ( !retainedChain )
2226 retainedChain = current_chain;
2228 std::cout <<
"New chain, delta = " << current_chain->
delta << std::endl;
2234 retainedChain = current_chain;
2236 std::cout <<
"New best chain, delta = " << current_chain->
delta << std::endl;
2242 std::cout <<
"chain rejected..." << std::endl;
2250 std::cout <<
"chain rejected, tabu and/or delta = " << current_chain->
delta << std::endl;
2258 std::cout <<
"no chain !!" << std::endl;
2264 if ( retainedChain )
2267 std::cout << it <<
" retained chain's degree: " << retainedChain->
degree;
2268 std::cout <<
" and delta: " << retainedChain->
delta << std::endl;
2271 for ( i = 0; i < retainedChain->
degree; i++ )
2273 fid = retainedChain->
feat[i];
2274 lid = retainedChain->
label[i];
2276 std::cout << fid <<
": " << sol[fid] <<
" -> " << lid <<
" Costs: " << inactiveCost[fid] <<
":" << ( sol[fid] != -1 ? labelpositions[sol[fid]]->cost : -1 ) <<
":" << ( lid != -1 ? labelpositions[lid]->cost : -1 ) << std::endl;
2279 if ( sol[fid] >= 0 )
2280 mLabelPositions.at( sol[fid] )->removeFromIndex( candidates_subsol );
2285 mLabelPositions.at( lid )->insertIntoIndex( candidates_subsol );
2287 tabu_list[fid] = it + tenure;
2289 std::cout <<
"fid: " << fid << std::endl;
2290 std::cout <<
"borderSize: " << borderSize << std::endl;
2291 std::cout <<
"lid: " << lid << std::endl;
2292 std::cout <<
"sub[fid]: " << sub[fid] << std::endl;
2293 std::cout <<
"inactivecosr[sub[fid]]: " << inactiveCost[sub[fid]] << std::endl;
2296 std::cout <<
"label[lid]: " << labelpositions[lid] << std::endl;
2297 std::cout <<
"label[lid]->cost: " << labelpositions[lid]->cost << std::endl;
2300 candidatesUnsorted[fid-borderSize]->
cost = ( lid == -1 ? inactiveCost[sub[fid]] : mLabelPositions.at( lid )->cost() );
2305 std::cout << std::endl;
2310 cur_cost += retainedChain->
delta;
2319 if ( best_cost - cur_cost >
EPSILON )
2322 std::cout <<
"new_best" << std::endl;
2324 best_cost = cur_cost;
2325 memcpy( best_sol, sol,
sizeof(
int ) * subSize );
2327 stop_it = ( it + itwimp > maxit ? maxit : it + itwimp );
2336 std::cout << it <<
" no chain" << std::endl << std::endl;
2342 memcpy( sol, best_sol,
sizeof(
int ) *subSize );
2344 for ( i = 0; i < probSize; i++ )
2345 delete candidates[i];
2347 delete[] candidates;
2348 delete[] candidatesUnsorted;
2350 for ( i = 0; i < subSize; i++ )
2351 featWrap[sub[i]] = -1;
2357 return initial_cost - best_cost;
2369 void Problem::check_solution()
2371 int *solution =
new int[nbft];
2383 candidates_sol->Search( amin, amax,
checkCallback, (
void* ) list );
2385 std::cerr <<
"Check Solution" << std::endl;
2389 for ( i = 0; i < nbft; i++ )
2392 if ( sol->s[i] >= 0 )
2396 if ( list->
size() != nbActive )
2398 std::cerr <<
"Error in solution !!!!" << std::endl;
2401 while ( list->
size() > 0 )
2404 int probFeatId = lp->getProblemFeatureId();
2405 if ( solution[probFeatId] >= 0 )
2407 std::cerr <<
"Doublon : " << probFeatId <<
" "
2408 << solution[probFeatId] <<
"<->"
2409 << lp->getId() << std::endl;
2412 solution[probFeatId] = lp->getId();
2416 for ( i = 0; i < nbft; i++ )
2418 if ( solution[i] != sol->s[i] )
2420 std::cerr <<
"Feat " << i <<
" : " << solution[i] <<
"<-->" << sol->s[i] << std::endl;
2439 int *wrap = ((
NokContext* ) context )->wrap;
2465 bool *ok =
new bool[nbft];
2471 clock_t start_time = clock();
2472 clock_t init_sol_time;
2473 clock_t search_time;
2484 context.
wrap = NULL;
2486 Chain *retainedChain;
2490 for ( i = 0; i < nbft; i++ )
2501 std::cout <<
" Compute initial solution: " << ( double )(( init_sol_time = clock() ) - start_time ) / (
double ) CLOCKS_PER_SEC;
2508 std::cerr <<
"\t" << sol->cost <<
"\t" << nbActive <<
"\t" << ( double ) nbActive / (
double ) nbft;
2509 std::cout <<
" (solution cost: " << sol->cost <<
", nbDisplayed: " << nbActive <<
"(" << double( nbActive ) / nbft <<
"%)" << std::endl;
2518 for ( seed = ( iter + 1 ) % nbft;
2519 ok[
seed] && seed != iter;
2520 seed = ( seed + 1 ) % nbft )
2529 iter = ( iter + 1 ) % nbft;
2532 std::cout <<
"Seed for it " << popit <<
" is " << seed << std::endl;
2535 retainedChain = chain( seed );
2537 if ( retainedChain && retainedChain->
delta < -
EPSILON )
2540 std::cout <<
"chain's degree & delta : " << retainedChain->
degree <<
" " << retainedChain->
delta << std::endl;
2543 for ( i = 0; i < retainedChain->
degree; i++ )
2545 fid = retainedChain->
feat[i];
2546 lid = retainedChain->
label[i];
2548 std::cout <<
" " << i <<
" :" << fid <<
" " << lid << std::endl;
2549 std::cout <<
" sol->s[fid]: " << sol->s[fid] <<
" <=> " << lid << std::endl;
2550 if ( sol->s[fid] == -1 || lid == -1 )
2551 std::cout <<
"feat inactive :" << inactiveCost[fid] << std::endl;
2552 if ( sol->s[fid] >= 0 )
2553 std::cout <<
"old cost : " << labelpositions[sol->s[fid]]->cost << std::endl;
2555 std::cout <<
"new cost : " << labelpositions[lid]->cost << std::endl;
2558 if ( sol->s[fid] >= 0 )
2566 candidates->Search( amin, amax,
nokCallback, &context );
2571 if ( sol->s[fid] >= 0 )
2573 mLabelPositions.at( lid )->insertIntoIndex( candidates_sol );
2578 sol->cost += retainedChain->
delta;
2580 std::cout <<
"Expected cost: " << sol->cost << std::endl;
2582 std::cout <<
"chain iteration " << popit <<
": " << sol->cost <<
", " << retainedChain->
delta <<
", " << retainedChain->
degree << std::endl;
2596 std::cout <<
"Cur_cost: " << sol->cost << std::endl;
2603 std::cout <<
" Improved solution: " << ( double )(( search_time = clock() ) - start_time ) / (
double ) CLOCKS_PER_SEC <<
" (solution cost: " << sol->cost <<
", nbDisplayed: " << nbActive <<
" (" << ( double ) nbActive / (
double ) nbft <<
"%)" << std::endl;
2606 std::cerr <<
"\tna\tchain" <<
"\tna\t" << popit <<
"\tna\t" << ( init_sol_time - start_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << ( search_time - init_sol_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << ( search_time - start_time ) / (
double ) CLOCKS_PER_SEC <<
"\t" << sol->cost <<
"\t" << nbActive <<
"\t" << ( double ) nbActive / (
double ) nbft;
2623 std::list<LabelPosition*> *solList =
new std::list<LabelPosition*>();
2630 for ( i = 0; i < nbft; i++ )
2632 if ( sol->s[i] != -1 )
2634 solList->push_back( mLabelPositions.at( sol->s[i] ) );
2636 else if ( returnInactive
2637 || mLabelPositions.at( featStartId[i] )->getFeaturePart()->layer()->displayAll()
2638 || mLabelPositions.at( featStartId[i] )->getFeaturePart()->getAlwaysShow() )
2640 solList->push_back( mLabelPositions.at( featStartId[i] ) );
2645 if ( returnInactive )
2659 stats->nbObjects = nbft;
2660 stats->nbLabelledObjects = 0;
2662 stats->nbLayers = nbLabelledLayers;
2663 stats->layersNbObjects =
new int[stats->nbLayers];
2664 stats->layersNbLabelledObjects =
new int[stats->nbLayers];
2666 for ( i = 0; i < stats->nbLayers; i++ )
2668 stats->layersName << labelledLayersName[i];
2669 stats->layersNbObjects[i] = 0;
2670 stats->layersNbLabelledObjects[i] = 0;
2675 for ( i = 0; i < nbft; i++ )
2677 lyrName = mLabelPositions.at( featStartId[i] )->getFeaturePart()->feature()->provider()->name();
2679 for ( j = 0; j < stats->nbLayers; j++ )
2681 if ( lyrName == stats->layersName[j] )
2689 stats->layersNbObjects[k]++;
2690 if ( sol->s[i] >= 0 )
2692 stats->layersNbLabelledObjects[k]++;
2693 stats->nbLabelledObjects++;
2705 void Problem::solution_cost()
2709 std::cout <<
"Global solution evaluation" << std::endl;
2721 context.
nbOv = &nbOv;
2722 context.
cost = &sol->cost;
2729 for ( i = 0; i < nbft; i++ )
2731 if ( sol->s[i] == -1 )
2733 sol->
cost += inactiveCost[i];
2739 lp = mLabelPositions.at( sol->s[i] );
2746 sol->cost += lp->
cost();
2754 if ( nbActive + nbHidden != nbft )
2756 std::cout <<
"Conflicts in solution: " << nbHidden / 2 << std::endl;
2758 std::cout <<
"nbActive and free: " << nbActive <<
" (" << double( nbActive ) / double( nbft ) <<
" %)" << std::endl;
2759 std::cout <<
"solution cost:" << sol->cost << std::endl;
double popmusic_tabu_chain(SubPart *part)
POPMUSIC, Tabu search with chain'.
bool falpCallback2(LabelPosition *lp, void *ctx)
static bool removeOverlapCallback(LabelPosition *lp, void *ctx)
struct pal::_nokContext NokContext
bool increaseNbOverlap(void *l, void *r)
int probSize
of features in problem
bool borderSizeInc(void *l, void *r)
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
bool increaseCost(void *tl, void *tr)
Thrown when something is added in a Full set.
double cost() const
Returns the candidate label position's geographical cost.
void popmusic()
popmusic framework
is slower and best than TABU, worse and faster than TABU_CHAIN
double popmusic_chain(SubPart *part)
POPMUSIC, chain.
struct pal::_elementary_transformation ElemTrans
void ignoreLabel(LabelPosition *lp, PriorityQueue *list, RTree< LabelPosition *, double, 2, double > *candidates)
void delete_chain(Chain *chain)
QLinkedList< int > * conflicts
double compute_subsolution_cost(SubPart *part, int *s, int *nbOverlap)
std::list< LabelPosition * > * getSolution(bool returnInactive)
is a little bit better than CHAIN but slower
void actualizeCandidateList(int nbOverlap, int *candidateListSize, double candidateBaseFactor, double *candidateFactor, int minCandidateListSize, double growingFactor, int n)
struct pal::_Triple Triple
bool isInConflict(LabelPosition *ls)
Check whether or not this overlap with another labelPosition.
SubPart * subPart(int r, int featseed, int *isIn)
int getId() const
return id
void getBoundingBox(double amin[2], double amax[2]) const
Return bounding box - amin: xmin,ymin - amax: xmax,ymax.
int getProblemFeatureId() const
void chain_search()
Test with very-large scale neighborhood.
bool subPartCallback(LabelPosition *lp, void *ctx)
void seed(uint32_t value)
double compute_feature_cost(SubPart *part, int feat_id, int label_id, int *nbOverlap)
void removeFromIndex(RTree< LabelPosition *, double, 2, double > *index)
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
double popmusic_tabu(SubPart *part)
bool increaseImportance(void *l, void *r)
bool checkCallback(LabelPosition *lp, void *ctx)
bool decreaseCost(void *tl, void *tr)
void insert(int key, double p)
RTree< LabelPosition *, double, 2, double > * candidates
struct pal::_subpart SubPart
QLinkedList< ElemTrans * > * currentChain
int * sub
wrap bw sub feat and main feat
bool updateCandidatesCost(LabelPosition *lp, void *context)
bool nokCallback(LabelPosition *lp, void *context)
void decreaseKey(int key)
void init_sol_empty()
Basic initial solution : every feature to -1.
bool chainCallback(LabelPosition *lp, void *context)
int subSize
total # features (prob + border)
void actualizeTabuCandidateList(int m, int iteration, int nbOverlap, int *candidateListSize, double candidateBaseFactor, double *candidateFactor, int minCandidateListSize, double reductionFactor, int minTabuTSize, double tabuFactor, int *tenure, int n)
LabelPosition is a candidate feature label position.
static bool compareLabelArea(pal::LabelPosition *l1, pal::LabelPosition *l2)
bool borderSizeDec(void *l, void *r)
double getNumOverlaps() const
QLinkedList< int > * queue
void sort(void **items, int N, bool(*greater)(void *l, void *r))
Sort an array of pointers.
SearchMethod
Search method to use.
int borderSize
of features bounding the problem
bool falpCallback1(LabelPosition *lp, void *ctx)
double * labelPositionCost
bool contains(const T &value) const
void append(const T &value)
int seed
first feat in sub part