博 士 （ 情 報 科 学 ） ABDUL‑RAHMAN OMAR ARIF

学 位 論 文題 名

Binary‑Real Coded Genetic Algorithm for Resource
Allocation Problem in Cloud Platforms（ 二進 実 数 複合 型 進化 計 算 によ る クラ ウド 資源割当 問題の解 決）

学位論文内容 の要旨
Cloud compu
ting is a promisingemerg
ing paradigmthat enablesenter
prisesto host multiple indepen‑derUapplicati
onson as
har
edre
sourc
epoolwit
hthea
bilit
yt
olea
seco
mputati
ona
lpow
erint
hefo
rmof
virtual mac
hineson a p
er‑demand bas
is. Resourceallocation in cloud platforms is a good example ofa com
plex real‑world problem. It isexpect
ed that an efficient resource managem
ent systemtoensurehighQualit
y of Se
rvice(QoS)underchallen
ging w
orkload variabilitytrends.Iftheend‑userda
taan
dapplications are moved to thecloud,cloudprovid
ers shouldgua
rante
ethea
vai
labil
it
yofthes
erv
ic
es
again
st unpredicta
ble system faults. It isalsoimport
ant t
oe
nh
anc
ethee
ffi
ci
enc
yofth
em
anage
me
nt
systems by optimizing power management, minimizing management system overhead, reducing oper‑
atio
ncos
tsan
dlim
it
ingt
hees
cal
at
inge
colo
gi
c
alf
o
ot
p
ri
n
to
fcl
o
udsy
ste
ms. F
ina
ll
y,vi
r
tu
ali
z
at
io
ni
san
enabl
ing technology thataddsgreatfiexibi
lit
yt
other
eso
ur
cema
nag
er
si
nadd
ressi
ngsu
chch
allen
ges.
Howev
er, utilizingvirtu
alization techniques efficiently is anew challenge of managem
ent c
omp
lexit
yad
dedt
ot
heab
ov
em
en
tio
nedc
ha
lle
ng
esofth
eclo
udpl
atfor
ms.
Many optimization problems inscience andengineeringinvolv
e constraints. Cons
traintoptim
izationproblems have a varietyof gr
eatc
hal
lenge
sres
ul
tin
gfro
mthev
ari
ou
sl
im
itso
nt
hede
ci
sio
nvar
ia
bles,
the c
on str
aint
si
nv
olv
ed,t
hein
terfe
renceamongcon
strai
nt
s,an
dt
hein
terre
latio
ns
hipb
etw
ee
nt
heco
n‑strai
nts and the objective functions. Geneticalg
orith
ms(GAs),onth
eoth
erha
nd,a
reef
fi
cie
ntse
arch
metah
eurist
ics that mimic theoperations ofnatur
al evo
lutio
n.GA
sp
laya
ninc
reasi
ng
lyim
por
ta
ntro
lein a variety of fields and ap
plications.However, cons
traintoptim
ization problems pose challengesto the performanceof GAs, sin
ce GAsin tbe
ir originalversions (i.e. theonesthat u
se tradi
ti
ona
lcr
ossov
erandmut
ati
onoperators)arebl
indt
oconstraints.
Thus,the main objectiveof th
is Ph.
D dissertationistodesi
gnanin
te
lli
ge
ntre
sou
rc
ea
ll
oca
ti
onma
n‑
ager that can flexibly adaptcomput
ational resources to satisfy the above mentioned challen
ges andob
jectives.Toaddressthisobjecti
ve,Ihavepr
opo
sed,first
ly, anove
lmu
lt
i‑lev
e
larc
hit
ect
ur
eth
atre
li
e
s
on ahybridvirtua
lization frameworkto add
ress the problemsof whatit isthe optimal.numb
erofVM
s
tobea
llo
ca
tedf
orther
un
nin
gapp
li
cat
io
ns?W
hati
ti
stheo
pti
ma
lu
ti
liz
at
ionl
eve
lstob
ea
ss
ign
edf
or
the running VMs? What it the optimal distribution to place the running VMs on?This framework canflexi
bly and effic
ientlyaddre
ss a wide spectrumof obj
ectives. Furt
hermore,Ihavedevelopedahy
bridGA, Binary‑Real coded Genetic Algonthm (BRGA), to act as acore for themanage
ment system intel‑
ligen
ce. BR
GA is anew hybridapproa
ch thathas t
he ability to handle bothfloat
ing point andbi
naryencoding schemes. It relies on a parameterized hybridschemeto sha
re thecompu
tational power andcoordinate the cooperation between Binary coded GA (BGA) and Real coded GA (RGA). BRGA has
beenapplie
d successfully to awidespectru
m of globaland co
nstraint optimization problemsfromthe

known benchmark suites. I have used CEC'2005 benchmark of 25 problems to verify the performanceof the algorithmagainstgloba
l optimization problems.To han
dle constraint optimization effectively, Ihave introduced a modified dynamic constraint handling technique within the architecture of BRGA.
I have also used the CEC'2010 benchmark suite of 18 functions toanalyz
e quality, time and scalabil‑
ity performance of BRGA. BRGA has been applied to the multi‑level autonomic architecture. I haveevaluated the feasibility, effectiveness and scalability of thepropose
d approach throughsimulationexperiments.
The dissertation organized as follows: Chapter l gives a general
introductionof theresea
rch. Itex‑plains the main motivation andmajorobjec
tives behindthe research. In ad
dition,it reviewsthe rel
atedliterature of BGAs and RGAs highlighting the main points of characteristics and disadvantages orcritiques. Chapter l also discusses the anatomy of hybrid algori
thms and clar
ifiesthe background ofresource allocation problem in cloud platforms. Chapter 2 is mai
nly about theBRGA.It describesthealgorithmic issues in details and discusses the conceptualissuesunderl
ine the oper
ationof BRGAandthe key concepts behind the success of BRGA.
Chapter 3 analyzes the performance of BRGA against global optimization problems through extensive
experimentation using the CEC'2005 benchmark suite of 25 functions. The outcomes of the parametertuning procedure are reported and analyzed. Quality and time performance of BRGA against original
binary and real coded GA components are reported and discussed.Finally, to v
alidate theperform
anceof BRGA, the performance of BRGA is compared with some other state‑of the‑art evolutionary al‑
gorithms from the literature. Chapter 4 analyzes the performance of BRGA against real parameter
constraint optimization problems through extensive experimentations using the CEC'2010 benchmark
suite of 18 functions. To extend BRGA for constraint optimization problems, a modi
fied dynamiccon‑straint handling technique is introduced within the architecture of the BRGA. The modified pen
alty
method is discussed in details here. To evaluate the affects of modification on BRGA performa
nce.
the outcomes of comparison experiments are reported and discussed. To validate the performance ofBRGA, the performance is compared with some other state‑of the‑art evolution
ary algorithms forcon‑
straint optimization problems. Finally, the outcomes of the parameter tuningproce
dure are reportedand analyzed.
Chapter 5 describ
es thepropos
ed multi‑level auto
nomicarchit
ecturein det
ail byillus
trating a general
overview of the system and defining key terminologies within the system. This Chapter discusses
the feasibility of architectu
re implementation and hig
hlights themain characte
ristics. Theunderl
ying
mixed integer mathematical model is presented and explained. To validate themainhypoth
esis ofthe
research, this Chapter reports the outcomes ofan ext
ensiveexper
imentalinves
tigation using theran‑
domly generated static datasets, which are snapshots that simulating challen
ging dynamicscenar
ios,
were used to evaluate the feas
ibility, effectiveness and scalability of our appr
oach throughsimulationexperiments. Finally, Chapter 6 and 7 conclude the dissertation. BRGA is a new hybrid approach. It
enjoys a competitive position when compared with the literature. Multi‑levelautonomic architec
ture
is a recent approach for the management of virtualized resources within cloud platforms.It hasthe
potential to impact the business environment of cloud computing.

― 564 ‑学位論文審査の要旨
主 査 教 授 棟 朝 雅 晴
副 査 教 授 赤 間
清
副 査 教 授 鈴 木 恵 二副 査 教 授 高 井 昌 彰

学 位 論 文 題名

Binaryー Real Coded Genetic Algorithm for ResourceAll
oca
tionProble
min ClouclPlatforms（二進実数複合型進化計算によるクラウド資源割当問題の解決）
クラウドコンピューティングにおいて、その資源をサービス要求に応じて適切に配分することは重要を課題であり、利用者からのサービス要求を満足するだけではをく、電カをどエネルギー効率の向上、システムのオーバーヘッドや管理コストの削減をど、さまざま教基準をもとに最適化を行う多目的最適化問題として定式化することができる。また、その決定変数においては数多くの実数と整数が混在しており、さまざまを制約条件を有することから、その解決は困難忽課題とをる。
本論文では、クラウドコンピューティングの資源最適配分問題において、上記の困難を課題を解決し柔軟かつ適切を資源配分を実現することを目的としている。そのために、
HorizontalS
calingにより実行すべきバーチャルマシンの最適数をまず決定し、さらにVerticalS
calingによりそれぞれのバーチャルマシンに割当てられる必要資源量を調整した後、割当先と教る物理資源を決定する、マルチレベルの管理アーキテクチャのフレームワークを提案した。このフレームワークにより、さまざまを条件に対して柔軟かつ効率的な資源割当が可能とをった。
さらに、実数と整数が混在した困難を最適化問題を解決するため、ニ進実数複合型進化計算アルゴリズムBRGA(
Binary‑RealcodedG
eneticAlgorithm）を提案した。BRGA
は実数 値により 符号化 されたGAと 、整数 値により 符号化さ れたGAを組み合わせた手法であり、それら両方のメカニズムを切り替えて最適化を行うことで、実数と整数が混合した幅広い最適化問題に対応することを目的としている。進化計算の分野で代表的をべンチ
マー ク問題で ある、 CEC
2005
ベン チマー ク問題、 および CEC
2010ベンチマーク問題に対し てBRG
Aを適用した結果、制約付きの困難教最適化問題に対して、その解の質、最適化効率、スケーラピリティにおいて優れた性能を示すことが確かめられた。最終的に、BRGAをマ ルチレベルのアーキテクチャに基づくクラウドコンピューティングの資源割
当 問題 に 適 用し 、 その 有 効 性を シ ミ ュレ ー ショ ン実 験を通し て検証し た。
本論文の構成は以下の通りである。第1章においては、本論文の背景とその目的につい−565一

て 述 べ て お り 、 従 来 型 の GAに つ い て そ の 特 徴 や 有 効 性 に つ い て 議 論 す る と と も に 、 ク ラ
ウ ド コ ンピ ュ ー テ ィン グ に お ける 資 源 割 当最 適 化 へ の適 用 に つ いて その背 景につ いて紹 介し た 。 第 2章 に お い て は 、 BRGAに つ い て そ の 遺 伝 的 操 作 等 、 ア ル ゴ リ ズ ム の 詳 細 に つい て 紹 介 し た 後 、 ア ル ゴ リ ズ ム 設 計 の 背 景 に あ る 考 え 方 に つ い て 議 論 し た 。 第 3章 に お いて は 、 BRGAの 性 能 に つ い て CEC2005ベ ン チ マ ー ク 問 題 に お け る 25の 関 数 最 適 化 の 結
果 に つ い て 報 告 し 、 BRGAと 従 来 型 の 高 性 能 と さ れ る GAと の 性 能 に つ い て 比 較 し 、 その 有 効 性 を 検 証 し た 。 第 4章 に お い て は 、 制 約 付 き の 実 数 値 最 適 化 問 題 の べ ン チ マ ー ク であ る CEC2010ベ ン チ マ ー ク 問 題 に お け る 18の 関 数 最 適 化 に BRGAを 適 用 し 、 制 約 条 件を 取 り 扱 う た め の 拡 張 を 行 う と と も に 、 BRGAと 従 来 型 の 高 性 能 と さ れ る GAと の 比 較に よ り 、 そ の 有 効 性 を 検 証 し た 。 第 5章 に お い て は 、 マ ル チ レ ベ ル の ア ー キ テ ク チ ャ を 提案 す る と と も に 、 そ の 資 源 最 適 割 当 問 題 に 対 し て BRGAを 適 用 し た シ ミ ュ レ ー シ ョ ン 実
験 を 行 い 、 提 案 手 法 の 妥 当 性 、 有 効 性 、 ス ケ ー ラ ピ リ テ ィ に つ い て 検 証 し た 。 第 6章 、第7章 に お い て は 、 結 論 と し て 、 BRGAは 実 数 値 と 整 数 値 に よ る 符 号 化 を 融 合 し た 新 た を 手法 で あ り、 ク ラ ウ ドコ ン ピ ュ ーテ ィ ン グ にお け る マ ルチ レ ベ ル アー キテク チャの 資源割 当
最 適 化 問題 に 対 す る有 効 を 解 決策 と を る こと を 確 め るて と が で きた 。結果 として クラウ ドコ ン ピ ュー テ ィ ン グに お い て 有用 を 最 適 化の フ レ ー ムワ ー ク お よび その解 決に必 要と毅 る
先 進 的 を進 化 計 算 アル ゴ リ ズ ムを 実 現 し たも の で あ り、 情 報 科 学の 分野に 貢献す るとこ ろ
大 を る もの が あ る 。よ っ て 著 者は 博 士 （ 情報 科 学 ） を授 与 さ れ る資 格ある ものと 認める 。

― 566―