Self-adaptive Ant Colony Algorithm for Real Estate Portfolio

Self-adaptive Ant Colony Algorithm for Real Estate Portfolio
Optimization based on Information Entropy*
ZHOU Shujing1, LI Yancang2
1.College of Civil Engineering, Hebei University of Engineering, Handan 056038, China.
2. College of Civil Engineering, Tianjin University, Tianjin300072, China.
Abstract
To find out an effective way to solve the real estate portfolio optimization, an improved
Ant Colony Algorithm based on information entropy was proposed. The information entropy was used
to control the path selection and evolutional strategy by self-adjusting to overcome the premature
convergence problem of the basic Ant Colony Algorithm. Simulation study on Traveling Salesman
Problem and the application results in the real estate portfolio optimization showed its efficiency. The
work has significance in theory and practice for solving the portfolio optimization and other
combinatorial optimization problems.
Key words
real estate; portfolio; Ant Colony Algorithm; information entropy; optimization
1 Introduction
The real estate circle is a filed where risks are as high as the potential rewards. How to control the
investment risk and improve the profitability of the project are urgent questions for the investors and the
real estate development companies. Real estate portfolio is an effective strategy of risk management.
The grounds of this method are “do not put your eggs into one basket”. But, in practice, it is difficult to
decide the proportion of every type. The portfolio theory is mature in stock market, yet they cannot be
directly used in real estate portfolio[1-2]. The tradition and improved real estate portfolio models and
algorithms have much deficiency, especially their calculations are complicated and results are not the
best solution.
The Ant Colony Optimization algorithms[3]proposed firstly by Italy scholars Dorigo.M,
Mahiezzo.V and Colorni.A in 1991 are new mode-based evolutionary meta-heuristic bionic algorithms,
and swarm intelligent algorithms for complex optimization, especially for the discrete NP-hard
complicated combinatorial optimization, e.g. TSP (Traveling Salesman Problem), JSP (Job-shop
Scheduling Problem), FSP (Flow shop Scheduling Problem), QAP(Quadratic Assignment Problem),
SOP(Sequential Ordering Problem), QOS multicast routing and little has been done for the search in
continuous-space problems.Yet because of the short development history and lack of rigorous theoretical
validation and practical implementation the basic ant colony algorithms have much deficiency,
especially it is easy to fall into the local best ,its calculation is complicated and its low efficiency in
solving the continuous-space problem.
To break through the limitations described above, an improved ant colony algorithm based on the
information entropy is proposed here. Self adaptively adjusting uses the information entropy, which is
related to the proceeding of the algorithm, to control the path selection and evolutional strategy. And the
improved algorithm can be employed in solving the real estate portfolio problems effectively.
2 The Improved Algorithm Proposed Here
The basic ant colony algorithm has many advantages: (1) using the positive feedback and
distribution calculation, the algorithm can easily realize the parallel computation. (2) It has strong
robustness and is easy to realize the combination with other improvement algorithms. (3) Compared
with the GA, the ACO can more easily to tackle the constraint. When the problem can be described by a
*
The Project is a Natural Science Research Directed Project of Hebei Education Administration (No.Z2003404),
China
1189
solution construction graph, its solution can be defined as a positive feedback course (e.g. the remained
pheromone in TSP), and the heuristic information can be got from the problem’s structure, the ant
colony algorithm can be employed. But basic ACO has much deficiency: (1) the calculation is
complicated. (2) It is easy to fall into stagnation. (3) It has law efficiency in solving the
continuous-space problem. (4) It lacks of rigorous theoretical validation and practical implementation.
Many learners have done a lot to overcome these shortcomings. Maniezzo.V etc. proposed, such as
the Ant-Q system, ACS, MAX-MIN Ant System and so on. [4]sumrize these modifications, which will
not be repeated. In some degree, all the improvements have done much good for the development of the
ant colony algorithm, yet people still have a lot work to do.
The basic ACO has four main parts: selection strategy, local pheromone update, local search
algorithm, and global pheromone update. The positive feedback theory in the selection strategy is to
reinforce the better solution, but it causes the stagnation behavior. This is the key to its shortage.
Because the quantity of each route has uncertainty, the information entropy, which relies on the
proceeding of the algorithm into the ACO to weigh the uncertainty above, can be introduced. Through
controlling the value of information entropy, people can control the route selection and the proportion of
the stochastic local perturbation behavior and can realize the self-adaptive of the algorithm. Define
pm =
τ m (t )
∑τ m (t )
，
where p m is the proportion of the pheromone of route m to the total
m∈s
n
pheromone, p m is the quantity of the route, p m≥0 ,
∑p
m =1
m
。
= 1 τ m (t ) is the pheromone quantity of
m route when the algorithm proceeds until the time of t , s is the solution space structured by all
routes. To eliminate the effect of sampling noise, a pheromone update rule with stronger robustness is
employed:
τ (t ) ← (1 − ρ )τ (t − 1) + ρ t −1τ * (t ) ，where τ * (t )
is the pheromone vector when time is
n
t . Define the information entropy as S (t ) = −k ∑ pi (t ) ln pi (t ) and can know the certainty of
i =1
m route being selected. This definition considers the characteristics of the ACO and combine the
proceeding time with the information entropy, which can realize the self-adaptively adjusting of the
algorithm: at the initial stage, each route has the equal pheromone and the information entropy is biggest.
With the pheromone reinforcement of some routes, the information entropy will reduce, if it was not
controlled, it will become zero and the pheromone is concentrated on one route which is taken regarded
as the best solution and causes stagnation behavior. Introduce α (′t ) =
where β (′t ) is the probability that the best route being remained and
S max − S (t )
α (′t )
S max
， β (′ ) = 1 − 2S1
t
max
is the proportion that the ants
which are allowed to follow the local pheromone update strategy in all the ants. At the early stage of
proceeding, the value of α (′t ) is small and with the process proceeding, the value becomes bigger in
order to explore the solution space in the beginning and reinforce the local search ability at final stage to
avoid stagnation. At the same time, β (′t ) is biggest at early stage to find the optimal route as many as
possible and later it becomes smaller to reinforce the function of random operation, which can also
avoid the stagnation.
The basic frame of the algorithm is shown in fig. 1
For the terminal principle, the general algorithms usually use the max iterative times. Here the
information entropy was introduced as the constraint termination because it is very difficult to decide the
max iterative times of the complicated problems. When the information entropy is smaller than a given
value (such as 0.01) the algorithm terminates and the solution is obtained.
1190
Initialization
Y
Whether terminal constraint
Print
N
Change the pheromone amount of each route
Compute the
s(t )
and
β (′t ) to find the possibly solution
Do mutation in the set in the proportion of α (′t )
Compute the value of
s(t )
Figure 1 the basic frame of the algorithm proposed in the paper
3 Performance Comparison of the Two Algorithms for TSP
To validate the efficiency of the algorithm proposed here, the bayes29 (29cities, 406routes) and
gr48 (48cities, 1128routes) of TSP that is the NP-hard combinatorial optimization with combinatorial
explosion were selected. Define α = 1.5, β = 4.0, ρ = 0.6, Q = 50 , and when the information
entropy is smaller than 0.01, the algorithm will terminate. To compare with the basic ant colony
algorithm, the comparison results were listed in Table 1.
From the comparison shown above, it can be seen that the basic ant colony algorithm is easy to fall
into stagnation yet the algorithm proposed here can break through this limitation and it can help the ants
step out of the stagnation and the heuristic information is very effective and its result is more optimal
than the basic ant colony algorithm.
Table 1 Performance comparison of the two algorithms for TSP
Basic ant colony algorithm
TSP
29
48
The algorithm proposed here
Time(s)
The optimal
solution
Time(s)
The optimal
solution
8
2180
5
2062
5494
33
5256
52
4 Application of the Improved Algorithm in Real Estate Portfolio Optimization
See the example: A real estate development company has six locations (A. B. C. D. E. F) to select
1191
in a city. The selectable types are (1) high level dwelling, (2) general resident, (3) mansion, (4)
apartments of commercial, (5) manufacturing housing. The economic evaluation index of every type in
every location is shown in Table 2, suppose the company select only one type in one location and give
the scheme of the portfolio.
To solve this problem, first calculate the information entropy of every combination,
S ′j = − p j ln p j , where S ′j is the information entropy of combination j , Pj =
Π j Rj
,
m
∑Π
k
Rk
k =1
n
Ri = ∑ xi rij , where m is the total number of types and n is the result numbers of profit. xi is the
j =1

m
∑x

= 1 .

Π j is the probability of profit
i =1

j , R i is the profit rate of type i (i = 1,2,L , m ) .
Known the S ′j , the improved algorithm proposed in the paper can be employed. The S ′j is used
proportion of investment in type i ,  0 ≤ xi ≤ 1,
i
as the heuristic information (equal to the distance d ij of TSP)and
η ij =
1
. two ants were used to
S′ij
search and when information entropy S (t ) is smaller than 0.01, calculation is stopped and the result is
got. The result is shown in Table 3.
Table 2 the economic evaluation index of every type in every location
high level dwelling
general resident
mansion
apartments of
commercial
NP
IRR PBP
V
manufacturing
housing
NP
IRR PBP
V
NP
V
IRR
PBP
NP
V
IRR
PBP
NP
V
IRR
PBP
A 44.4
34.7
7.5
15.1
57.0
5.3
70.5
42.0
3.1
43.3
70.0
3.2
6.5
26.0
5.0
B 52.6
67
3.7
6.2
62.0
3.2
44.7
45.0
2.9
52.8
56.0
4.5
12.2
12.0
4.6
C 13.8
40.0
5.6
20.3
39.0
4.5
5.6
27.0
4.6
15.5
48.0
3.9
11.3
37.0
5.2
D 35.6
31.0
6.3
8.7
70.0
5.0
33.9
19.0
5.7
41.3
52.0
3.7
4.4
25.0
3.7
E
25
55
5.1
30.3
57.0
5.3
51.7
36.0
4.8
57.5
18.0
3.0
7.9
40.0
4.3
F
55
47
7.0
12.7
62.0
4.8
53.3
34.0
4.2
62.7
58.0
3.8
17.4
47.0
3.8
Table 3 the calculation results
Results
（1）location B
type（2）location E
type（3）location A
type（4）location F
type（5） location C
type
NPV
IRR
PBP
Investment
proportion
52.6
67
3.7
21.0
30.3
57
5.3
13.4
70.5
42
3.1
25.2
62.7
58
3.8
21.8
11.3
37
5.2
18.6
1192
The application result demonstrates that the improved algorithm proposed here can reach the global
optimal result that meets our requirement. It is effective in solving the real estate portfolio optimization
and its calculation is easier.
5 Conclusions
(1) The simulation study demonstrates that, the strategy of using information entropy to control the
route selection and evolution realizes the self adaptively adjusting and avoid the stagnation behavior.
(2) The improved algorithm presented here has good convergence and stability. And it can
effectively solve the real estate portfolio optimization problem. The algorithm has strong robustness and
being slightly improved, it can be employed to solve other combinatorial optimization problems. It is
superior to the basic ant colony algorithm.
References
[1] Pagliari Joseph. L. The Handbook of Real Estate Portfolio Management. RICHARD D.IRWIN, Inc,1995
[2] Cheng Siwei Venture Capital Business in China, Beijing,2000
[3] Dorigo M Maniezzo V Colorni A. The Ant System: An autocatalytic optimizing process. Technical Report.
91-106 revised, Department of Electronic, Politecnico of Milano, Milan, Italy, 1991
[4] Li Yancang Study on decision-making of real estate portfolio based on information entropy and improved ACO,
Hebei Institute of Engineering, 2005
，
，
The author can be contacted from e-mail : [email protected]
1193