Ouvrir le menu
Publier un document
Alternate Text
clear
fr
Ouvrir le menu
Central Public Sector Enterprises
19 pages
English

Central Public Sector Enterprises

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
19 pages
English
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

  • revision - matière potentielle : second pay
  • exposé
Issue 1 Volume 1 Central Public Sector Enterprises October-December, 2009 Department of Public Enterprises Ministry of Heavy Industries and Public Enterprises Q U A R T E R L Y N E W S L E T T E R
  • dpe
  • cpses
  • tiss
  • public enterprises
  • training programme
  • complex
  • win win situation
  • win- win situation
  • win-win situation
  • india
  • 2 india
  • staff
  • government

Sujets

Exposé

Informations

Publié par
Nombre de lectures 6
Langue English

Extrait

Probabilistic GRASP-Tabu Search Algorithms
for the UBQP problem
a b c a,∗Yang Wang , Zhipeng Lu¨ , Fred Glover Jin-Kao Hao
aLERIA, Universit´e d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France
bSchool of Computer Science and Technology, Huazhong University of Science and
Technology, 430074 Wuhan, China
cOptTek Systems, Inc., 2241 17th Street Boulder, CO 80302, USA
Accepted to Computers and Operations Research, Dec. 2011.
DOI: 10.1016/j.cor.2011.12.006
Abstract
This paper presents two algorithms combining GRASP and TabuSearch for solving
the Unconstrained Binary Quadratic Programming (UBQP) problem. We first pro-
pose a simple GRASP-Tabu Search algorithm working with a single solution and
thenreinforceitbyintroducingapopulationmanagementstrategy.Bothalgorithms
arebasedonadedicatedrandomizedgreedyconstructionheuristicandatabusearch
procedure. We show extensive computational results on two sets of 31 large random
UBQP instances and one set of 54 structured instances derived from the MaxCut
problem. Comparisons with state-of-the-art algorithms demonstrate the efficacy of
our proposed algorithms in terms of both solution quality and computational effi-
ciency. It is noteworthy that the reinforced GRASP-Tabu Search algorithm is able
to improve the previous best known results for 19 MaxCut instances.
Keywords:GRASP;TabuSearch;UBQP;PathRelinking;PopulationManagement;
MaxCut
1 Introduction
The objective of the unconstrained binary quadratic programming problem is
to maximize the function:
∗ Corresponding author.
Email addresses: yangw@info.univ-angers.fr (Yang Wang),
zhipeng.lv@hust.edu.cn (Zhipeng Lu¨), glover@opttek.com (Fred Glover),
hao@info.univ-angers.fr (Jin-Kao Hao).
Preprint submitted to Elsevier 4 January 2012n nXX
′f(x) = xQx = q x x (1)ij i j
i=1 j=1
where Q = (q ) is an n×n matrix of constants and x is an n-vector of binaryij
(zero-one) variables, i.e., x ∈{0,1}, i = 1,...,n.i
The UBQP is notable for its ability to formulate a wide range of important
problems, including those from financial analysis [23], social psychology [16],
machine scheduling [1], computer aided design [20] and cellular radio channel
allocation [9]. Besides, due to the ability to incorporate quadratic infeasibility
constraintsintotheobjectivefunctioninanexplicitmanner,UBQPenablesit-
selftoserveasacommonmodelforawiderangeofcombinatorialoptimization
problems. A review of additional applications and the re-formulation proce-
dures can be found in [19] demonstrating the utility of UBQP for a variety of
applications.
During the last two decades, a large number of procedures for solving the
UBQP have been reported in the literature. Among them are several exact
methods using branch and bound or branch and cut (see, e.g., [6,17,30]). Due
tothefactthattheexactmethodsbecomeprohibitivelyexpensivetoapplyfor
solvinglargeinstances,variousmetaheuristicalgorithmshavebeenextensively
used to find high-quality solutions to large UBQP instances in an acceptable
time. Some representative metaheuristic methods include local search heuris-
tics [7], Simulated Annealing [4,18]; adaptive memory approaches based on
Tabu Search [14,15,27,29]; population-based approaches such as Evolutionary
Algorithms [5,21,25], Scatter Search [2] and Memetic Algorithms [22,26].
This paper presents two algorithms for the UBQP that combine GRASP and
TabuSearch.Thefirst,GRASP-TS,usesabasicGRASPalgorithmwithsingle
solution search while the other, GRASP-TS/PM, launches each tabu search
by introducing a population management strategy based on an elite reference
set. In GRASP-TS/PM we pick a single solution at a time from the refer-
ence set, and operate on it, utilizing the ideas of “elite solution recovery” and
“probabilistic evaluation” proposed in [12,37]. Our experimental testing dis-
closesthatGRASP-TS/PMyieldsverycompetitiveoutcomesonalargerange
of both random and structured problem instances.
To assess the performance and the competitiveness of our algorithms in terms
of both solution quality and efficiency, we provide computational results on
31 large random benchmark instances with up to 7000 variables as well as 54
instances derived from the MaxCut problem.
2The remaining part of the paper is organized as follows. Sections 2 and 3 de-
scriberespectivelythebasicGRASP-TabuSearchalgorithmandtheGRASP-
Tabu Search algorithm with Population Management. Section 4 is dedicated
to the computational results and detailed comparisons with other state-of-
the-art algorithms in the literature. Finally, concluding remarks are given in
Section 5.
2 GRASP-Tabu Search
2.1 General GRASP-TS procedure
The GRASP algorithm is usually implemented as a multistart procedure
[31,32], consisting of a randomized greedy solution construction phase and
a sequel local search phase to optimize the objective function as far as possi-
ble. These two phases are carried out iteratively until a stopping condition is
satisfied.
Our basic GRASP-Tabu Search algorithm (denoted by GRASP-TS) for the
UBQP follows this general scheme (see Algorithm 1) and uses a dedicated
greedy heuristic for solution construction (see Section 2.2) as well as tabu
search (see Section 2.3) as its local optimizer.
Algorithm 1 Pseudo-code of GRASP-TS for UBQP
1: Input: matrix Q
∗ ∗2: Output: the best binary n-vector x found so far and its objective value f
∗3: f =−∞
4: repeat
05: Construct a greedy randomized solution x /∗ Section 2.2∗/
′ 06: x ← Tabu Search(x ) /∗ Section 2.3∗/
′ ∗7: if f(x) > f then
∗ ′ ∗ ′8: x = x , f = f(x)
9: end if
10: until a stopping criterion is met
2.2 Solution Construction
GRASP-TS constructs a new solution at each step according to a greedy ran-
dom construction heuristic, which was originally used in probabilistic Tabu
Search (PTS) [12,36,37] and motivated by the fact that the GRASP construc-
tion resembles this PTS approach.
36
The construction procedure consists of two phases: one is to adaptively and
iteratively select some variables to receive the value 1; the other is to assign
the value 0 to the left variables. Starting with an empty solution, a variable
x with the maximum q is picked as the first element of the partial solution.i ii
Giventhepartialsolutionpx ={x ,x ,...,x },indexedbypi ={k ,k ,...,k},k k k 1 2 α1 2 α
we calculate its objective function value (OFV) as:
X X
OFV(px) = (q + q ·x ) (2)ii ij j
i∈pi,x =1 j∈pi,j=ii
Ateachiterationofthefirstphasewechooseoneunassignedvariableaccording
toagreedyfunctionandthenassignvalue1toit.Specifically,wecalculatethe
objectivefunctionincrement(OFI)tothepartialsolutionpxifoneunassigned
variable x (j∈ N\pi) is added into px with value 1.j
X
OFI (px) = q + (q ·x ) (3)j jj ij i
i∈pi
At each step, all the unassigned variables are sorted in an non-increasing
order according to their OFI values. Note that we only consider the first rcl
variables having non-negative OFI values, where rcl is called the restricted
rcandidatelistsize.Ther-thrankedvariableisassociatedwithabiasb = 1/e .r
Therefore, the r-th ranked variable is selected with probability p(r) that is
calculated as follows:
rclX
p(r) = b / b (4)r j
j=1
Once a variable x is selected and added into the partial solution px withj
the assignment value 1, the partial solution px and its index pi, its objec-
tive function value OFV(px) and the left variables’ OFI values are updated
correspondingly as follows:
′ ′px = px∪{x}, pi = pi∪{j} (5)j
′OFV(px) = OFV(px)+OFI (px) (6)j
′For any variable x (k∈ N\pi),k
′OFI (px) = OFI (px)+q (7)k k jk
This procedure repeats until all the OFI values of the unassigned variables
are negative. Then, the new solution is completed by assigning the value 0 to
all the left variables.
42.3 Tabu Search Procedure
When a new solution is fully constructed, we apply the tabu search procedure
described in [22] to optimize this solution. Our TS algorithm is based on a
simple one-flip move neighborhood, which consists of changing (flipping) the
value of a single variable x to its complementary value 1−x . Each time ai i
move is carried out, the reverse move is forbidden for the next TabuTenure
iterations. In our implementation, we selected to set the tabu tenure by the
assignmentTabuTenure(i) = ttc+rand(10),wherettcisagivenconstantand
rand(10) takes a random value from 1 to 10. Once a move is performed, one
needs just to update a subset of move values affected by the move. Accompa-
nying this rule, a simple aspiration criterion is applied that permits a move
to be selected in spite of being tabu if it leads to a solution better than the
current best solution. Our TS method stops when the best solution cannot
be improved within a given number μ of moves and we call this number the
improvement cutoff. Interested readers are referred to [22] for more details.
3 GRASP-Tabu Search with Population Management
3.1 General GRASP-TS/PM procedure
Starting from the basic GRASP-TS algorithm, we introduce additional en-
hancements using the idea of maintaining a pool of elite solutions. By com-
bining GRASP-TS with the population management strategy, our reinforced
GRASP-TS/PM algorithm offers a better balance between intensification and
diversification as a means of exploiting the search space. The general archi-

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Signaler un problème
playstore
appstore
facebook twitter instagram youtube

YouScribe

Le catalogue

Le service

Les conditions

© 2010-2024 YouScribe
Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts