研究者データベース

研究者情報

マスター

アカウント(マスター)

  • 氏名

    棟朝 雅晴(ムネトモ マサハル), ムネトモ マサハル

所属(マスター)

  • 情報基盤センター システムデザイン研究部門

所属(マスター)

  • 情報基盤センター システムデザイン研究部門

独自項目

syllabus

  • 2021, 情報システム設計学特論, Information Systems Design, 修士課程, 情報科学研究科, 進化計算,メタヒューリスティクス
  • 2021, 情報システム設計学特論, Information Systems Design, 修士課程, 情報科学院, 進化計算,メタヒューリスティクス
  • 2021, 情報システム設計学特論, Information Systems Design, 博士後期課程, 情報科学研究科, 進化計算,メタヒューリスティクス
  • 2021, 情報システム設計学特論, Information Systems Design, 博士後期課程, 情報科学院, 進化計算,メタヒューリスティクス
  • 2021, アニメーション工学, Animation Engineering, 学士課程, 工学部, メディアコンテンツ,符号化,形態素解析,機械翻訳,サポートベクターマシン,情報可視化,拡張現実(AR),仮想現実(VR),ビジョンベースAR,インタラクティブメディア
  • 2021, メディアコンテンツ工学, Media Content Engineering, 学士課程, 工学部, メディアコンテンツ,符号化,形態素解析,機械翻訳,サポートベクターマシン,情報可視化,拡張現実(AR),仮想現実(VR),ビジョンベースAR,インタラクティブメディア
  • 2021, 情報理工学演習Ⅰ, Exercise in Computer Science and Information Technology I, 学士課程, 工学部, コンピュータシステム、ネットワークとクラウド、計算機アーキテクチャ、オペレーティングシステム、コンピュータネットワーク、Web技術、クラウド技術
  • 2021, ネットワークとクラウド, Computer Networks and Cloud Computing, 学士課程, 工学部, ネットワーク階層化、TCP/IP、 カプセル化、 経路制御、DNS、 ネットワークアプリケーション、 クラウド

PositionHistory

  • 教育研究評議会評議員, 2019年4月1日, 2021年3月31日
  • 教育研究評議会評議員, 2021年4月1日, 2023年3月31日
  • 研究戦略室室員, 2023年4月1日, 2024年3月31日
  • 情報基盤センター副センター長, 2013年4月1日, 2015年3月31日
  • 情報基盤センター副センター長, 2015年4月1日, 2017年3月31日
  • 情報基盤センター副センター長, 2017年4月1日, 2019年3月31日
  • 情報基盤センター長, 2019年4月1日, 2021年3月31日
  • 情報基盤センター長, 2021年4月1日, 2023年3月31日
  • 情報基盤センター長, 2023年4月1日, 2025年3月31日

researchmap

プロフィール情報

所属

  • 大学院情報科学院, 教授

学位

  • 博士(工学)(北海道大学)

プロフィール情報

  • 棟朝, ムネトモ
  • 雅晴, マサハル
  • ID各種

    200901037594718436

対象リソース

所属

  • 大学院情報科学院, 教授

業績リスト

研究キーワード

  • クラウドコンピューティング   並列分散処理   システム設計   進化計算   Parallel and distributed processing   Systems design   Evolutionary computation   

研究分野

  • 情報通信 / 情報ネットワーク
  • 情報通信 / 計算機システム
  • 情報通信 / 高性能計算
  • 情報通信 / 知能情報学
  • 情報通信 / ソフトウェア
  • 情報通信 / 感性情報学
  • 情報通信 / ソフトコンピューティング

経歴

  • 2024年04月 - 現在 北海道大学 副理事
  • 2024年04月 - 現在 北海道大学 情報環境推進本部 副本部長
  • 2019年04月 - 現在 北海道大学 教育研究評議会 評議員
  • 2019年04月 - 現在 北海道大学 情報環境推進本部 情報化推進室長
  • 2019年04月 - 現在 北海道大学 情報基盤センター センター長
  • 2015年10月 - 現在 国立情報学研究所 客員教授
  • 2012年08月 - 現在 北海道大学 教授
  • 2013年04月 - 2019年03月 北海道大学 情報基盤センター 副センター長
  • 2007年04月 - 2012年07月 北海道大学 准教授
  • 2007年 - 2009年 国立情報学研究所 客員准教授
  • 1999年10月 - 2007年03月 北海道大学 助教授
  • 1996年04月 - 1999年09月 北海道大学 助手
  • 1998年06月 - 1999年03月 イリノイ大学アーバナシャンペイン校 客員研究員

委員歴

  • 2022年10月 - 現在   進化計算学会   会長
  • 2019年04月 - 現在   国立情報学研究所   学術情報ネットワーク運営・連携本部委員
  • 2014年11月 - 現在   日本MSP(Managed Service Provider)協会   発起人・顧問
  • 2013年02月 - 現在   7大学情報基盤センター   クラウドコンピューティング研究会 主査
  • 2019年04月 - 2023年03月   情報処理学会   論文誌「数理モデル化と応用」編集委員長
  • 2020年10月 - 2022年09月   進化計算学会   理事・副会長
  • 2017年05月 - 2021年04月   大学ICT推進協議会   理事
  • 2020年04月 - 2021年03月   クラウド利用促進機構   総合アドバイザー
  • 2019年04月 - 2021年03月   国立大学共同利用・共同研究協議会   会計監事
  • 2017年04月 - 2019年03月   情報処理学会   北海道支部長
  • 2016年04月 - 2019年03月   情報処理学会   論文誌「数理モデル化と応用」副編集委員長
  • 2015年03月 - 2019年03月   情報処理学会   数理モデル化と問題解決研究会 運営委員
  • 2013年01月 - 2019年03月   Open Compute Project Japan   発起人・運営委員
  • 2012年09月 - 2019年03月   クラウド利用促進機構   総合アドバイザー
  • 2014年04月 - 2017年04月   大学ICT推進協議会   クラウド部会 主査
  • 2013年04月 - 2017年03月   情報処理学会   マルチメディア通信と分散処理研究会運営委員
  • 2013年04月 - 2017年03月   情報処理学会   ハイパフォーマンスコンピューティング研究会 運営委員
  • 2014年04月 - 2015年03月   オープンクラウド実証実験タスクフォース   発起人・運営委員
  • 2013年04月 - 2015年03月   グリッド協議会   運営委員
  • 2013年04月 - 2015年03月   情報処理学会   数理モデル化と問題解決研究会 主査
  • 2012年04月 - 2014年03月   大学ICT推進協議会   クラウド部会 副主査
  • 2010年04月 - 2013年09月   進化計算学会   監事   進化計算学会
  • 2011年04月 - 2013年03月   情報処理学会   北海道支部 評議員   情報処理学会
  • 2009年04月 - 2013年03月   情報処理学会   数理モデル化と問題解決研究会 幹事   情報処理学会
  • 2009年04月 - 2013年03月   情報処理学会   計算機アーキテクチャ研究会 運営委員   情報処理学会
  • 2009年04月 - 2011年03月   情報処理学会   北海道支部 幹事   情報処理学会
  • 2007年04月 - 2011年03月   情報処理学会   マルチメディア通信と分散処理研究会 運営委員   情報処理学会
  • 2007年04月 - 2011年03月   情報処理学会   ハイパフォーマンスコンピューティング研究会 運営委員   情報処理学会
  • 2002年04月 - 2006年03月   情報処理学会   マルチメディア通信と分散処理研究会 運営委員   情報処理学会
  • 2001年04月 - 2005年03月   情報処理学会   計算機アーキテクチャ研究会 運営委員   情報処理学会

受賞

  • 2023年10月 情報処理学会 コンピュータサイエンス領域功績賞
  • 2017年09月 情報処理学会数理モデル化と問題解決研究会 功績賞
     
    受賞者: 棟朝 雅晴
  • 2009年03月 The 10-th WSEAS international conference on Evolutionary Computation Best paper award
     
    受賞者: MUNETOMO Masaharu

論文

  • Enzhi Zhang, Bochen Dong, Mohamed Wahib, Rui Zhong, Masaharu Munetomo
    J. Supercomput. 80 9 12644 - 12662 2024年06月
  • Rui Zhong, Enzhi Zhang, Masaharu Munetomo
    J. Supercomput. 80 9 12186 - 12217 2024年06月
  • Rui Zhong, Enzhi Zhang, Masaharu Munetomo
    Complex and Intelligent Systems 10 2 2129 - 2149 2024年04月 
    This paper proposes a novel algorithm named surrogate ensemble assisted differential evolution with efficient dual differential grouping (SEADECC-EDDG) to deal with large-scale expensive optimization problems (LSEOPs) based on the CC framework. In the decomposition phase, our proposed EDDG inherits the framework of efficient recursive differential grouping (ERDG) and embeds the multiplicative interaction identification technique of Dual DG (DDG), which can detect the additive and multiplicative interactions simultaneously without extra fitness evaluation consumption. Inspired by RDG2 and RDG3, we design the adaptive determination threshold and further decompose relatively large-scale sub-components to alleviate the curse of dimensionality. In the optimization phase, the SEADE is adopted as the basic optimizer, where the global and the local surrogate model are constructed by generalized regression neural network (GRNN) with all historical samples and Gaussian process regression (GPR) with recent samples. Expected improvement (EI) infill sampling criterion cooperated with random search is employed to search elite solutions in the surrogate model. To evaluate the performance of our proposal, we implement comprehensive experiments on CEC2013 benchmark functions compared with state-of-the-art decomposition techniques. Experimental and statistical results show that our proposed EDDG is competitive with these advanced decomposition techniques, and the introduction of SEADE can accelerate the convergence of optimization significantly.
  • Rui Zhong, Jun Yu, Chao Zhang 0030, Masaharu Munetomo
    Neural Comput. Appl. 36 12 6721 - 6740 2024年04月
  • Rui Zhong, Binnan Tu, Enzhi Zhang, Masaharu Munetomo
    Evolutionary Intelligence 2024年 
    This paper proposes a novel decomposition method named Adjacent Intensity Matrix with Linkage Identification (ALI) which collaborates with the Cooperative Coevolution (CC) framework to solve large-scale optimization problems (LSOPs) in noisy environments. Conventional Differential Grouping (DG)-based methods in the CC framework can detect the interactions by the absolute interaction intensity. In noisy environments, the uncertainty of fitness will be amplified and the absolute interaction intensity is easily larger than the threshold, which results in all decision variables being grouped into one component. Although it is difficult to detect interactions through absolute interaction intensity in noisy environments, the relative difference between separable and non-separable decision variables may exist, which can help us determine the separability to form the sub-components. We propose the Adjacent Intensity Matrix (AIM) by an additive identification criterion and determine the significant intensity (SI) to classify the interactions by learning the regularity of intensity. Since the conventional performance indicator of decomposition accuracy (DA) cannot fully reflect the inner structure of a non-separable sub-component, we introduce a more rigorous metric to evaluate the decomposition named the similarity of dependency structure matrix (SDSM). In the optimization phase after the decomposition, we employ an advanced optimizer named Modified Differential Evolution with Distance-based Selection (MDE-DS) to adapt to noisy environments. Experimental results on the CEC2013 Suite with noise show that our proposal has a broad prospect to solve LSOPs in noisy environments.
  • Enzhi Zhang, Mohamed Wahib, Rui Zhong, Masaharu Munetomo
    J. Adv. Comput. Intell. Intell. Informatics 28 1 67 - 78 2024年01月
  • Rui Zhong, Fei Peng, Jun Yu, Masaharu Munetomo
    Alexandria Engineering Journal 87 148 - 163 2024年01月 
    Vegetation evolution (VEGE) is a newly proposed meta-heuristic algorithm (MA) with excellent exploitation but relatively weak exploration capacity. We thus focus on further balancing the exploitation and the exploration of VEGE well to improve the overall optimization performance. This paper proposes an improved Q-learning based VEGE, and we design an exploitation archive and an exploration archive to provide a variety of search strategies, each archive contains four efficient and easy-implemented search strategies. In addition, online Q-Learning, as well as ε-greedy scheme, are employed as the decision-maker role to learn the knowledge from the past optimization process and determine the search strategy for each individual automatically and intelligently. In numerical experiments, we compare our proposed QVEGE with eight state-of-the-art MAs including the original VEGE on CEC2020 benchmark functions, twelve engineering optimization problems, and wireless sensor networks (WSN) coverage optimization problems. Experimental and statistical results confirm that the proposed QVEGE demonstrates significant enhancements and stands as a strong competitor among existing algorithms. The source code of QVEGE is publicly available at https://github.com/RuiZhong961230/QVEGE.
  • Rui Zhong, Jun Yu, Chao Zhang, Masaharu Munetomo
    International Journal of Computational Intelligence Systems 16 1 2023年12月 
    This paper proposes a novel surrogate ensemble-assisted hyper-heuristic algorithm (SEA-HHA) to solve expensive optimization problems (EOPs). A representative HHA consists of two parts: the low-level and the high-level components. In the low-level component, we regard the surrogate-assisted technique as a type of search strategy and design the four search strategy archives: exploration strategy archive, exploitation strategy archive, surrogate-assisted estimation archive, and mutation strategy archive as low-level heuristics (LLHs), each archive contains one or more search strategies. Once the surrogate-assisted estimation archive is activated to generate the offspring individual, SEA-HHA first selects the dataset for model construction from three principles: All Data, Recent Data, and Neighbor, which correspond to the global and the local surrogate model, respectively. Then, the dataset is randomly divided into training and validation data, and the most accurate model built by polynomial regression (PR), support vector regression (SVR), and Gaussian process regression (GPR) cooperates with the infill sampling criterion is employed for solution estimation. In the high-level component, we design a random selection function based on the pre-defined probabilities to manipulate a set of LLHs. In numerical experiments, we compare SEA-HHA with six optimization techniques on 5-D, 10-D, and 30-D CEC2013 benchmark functions and three engineering optimization problems with only 1000 fitness evaluation times (FEs). The experimental and statistical results show that our proposed SEA-HHA has broad prospects for dealing with EOPs.
  • Daichi Morimoto, Haruhi Tsukamoto, Motoaki Hiraga, Kazuhiro Ohkura, Masaharu Munetomo
    Artificial Life and Robotics 28 4 661 - 668 2023年11月 
    This paper demonstrates a controller design of a multi-legged robotic swarm in a rough terrain environment. Many studies in swarm robotics are conducted with mobile robots that work in relatively flat fields. This paper focuses on a multi-legged robotic swarm, which is expected to operate not only in a flat field but also in rough terrain environments. However, designing a robot controller becomes a challenging problem because a designer has to consider how to coordinate a large number of joints in a robot, besides the complexity of a swarm problem. This paper employed an evolutionary robotics approach for the automatic design of a robot controller. The experiments were conducted by computer simulations with the path formation task. The results showed that the proposed approach succeeds in generating collective behavior in flat and rough terrain environments.
  • Rui Zhong, Fei Peng, Enzhi Zhang, Jun Yu, Masaharu Munetomo
    Biomimetics 8 6 2023年10月 
    We introduce two new search strategies to further improve the performance of vegetation evolution (VEGE) for solving continuous optimization problems. Specifically, the first strategy, named the dynamic maturity strategy, allows individuals with better fitness to have a higher probability of generating more seed individuals. Here, all individuals will first become allocated to generate a fixed number of seeds, and then the remaining number of allocatable seeds will be distributed competitively according to their fitness. Since VEGE performs poorly in getting rid of local optima, we propose the diverse mutation strategy as the second search operator with several different mutation methods to increase the diversity of seed individuals. In other words, each generated seed individual will randomly choose one of the methods to mutate with a lower probability. To evaluate the performances of the two proposed strategies, we run our proposal (VEGE + two strategies), VEGE, and another seven advanced evolutionary algorithms (EAs) on the CEC2013 benchmark functions and seven popular engineering problems. Finally, we analyze the respective contributions of these two strategies to VEGE. The experimental and statistical results confirmed that our proposal can significantly accelerate convergence and improve the convergence accuracy of the conventional VEGE in most optimization problems.
  • Enzhi Zhang, Ruqin Wang, Mohamed Wahib, Rui Zhong, Masaharu Munetomo
    Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics 899 - 904 2023年 
    When training neural networks, the weights of the model are updated at each optimization step, and the older weights are discarded. In this paper, we propose a method called, Training Knowledge Inheritance (TKI), to use the knowledge about the progression of weight and loss data in reducing overfitting and improving the generalization in the later stages of training. We reformulate the traditional gradient optimization problem as a reinforcement learning task. In particular, by treating the trainable weight space as an environment, the learning rate as action, and the validation accuracies as the rewards, we train a Q-network (controller) to learn the discounted future validation accuracy and guide the later training of another network (worker). We conduct the experiments on the MNIST, CIFAR-10, and CIFAR-100 datasets with naive dense neural networks and ResNet-56. Our results show that TKI could rediscover learning rate schedule rules similar to previous works, including increasing, decaying, and cyclical repeating.
  • Enzhi Zhang, Bochen Dong, Mohamed Wahib, Rui Zhong, Masaharu Munetomo
    Proceedings - 2023 Congress in Computer Science, Computer Engineering, and Applied Computing, CSCE 2023 2218 - 2225 2023年 
    This paper proposes a method called Meta Gener-ative Data Augmentation Optimization (MGDAO) to overcome limitations in existing data augmentation techniques. While traditional data augmentation methods have relied on expert intuition to determine effective transformations, recent approaches have attempted to generate data augmentation strategies automatically. However, these automatic methods can still suffer from limited operation sets, high computational costs, or difficulty in training conditional generative models. To address these issues, MGDAO replaces the limited operations space in the AutoAugment series with a deep-style generator and replaces the discriminator in a generative adversarial model with the validation loss of the target model. The generator learns to transform the data from the training domain to the validation data domain. It is further used to generate data-augmented samples to train the target model and reduce the validation loss. Experiments on few-shot image classification benchmarks show that MGDAO achieves competitive results compared to existing data auto-augmentation methods.
  • Rui Zhong, Enzhi Zhang, Masaharu Munetomo
    Proceedings - 2023 Congress in Computer Science, Computer Engineering, and Applied Computing, CSCE 2023 2153 - 2160 2023年 
    In this paper, we propose a novel hyper-heuristics algorithm named Evolutionary Multi-mode Slime mould Op-timization (EMSMO) inspired by the slime mould foraging behaviors for continuous optimization. The EMSMO is a com-bination of High-Level and Low-Level components. In the Low-Level component, we formulate the foraging behaviors of slime mould and design four generation strategies: Search for food, Approach food, Wrap food, and Re-initialization. In the High-Level component, we design an improvement-based probabilistic selection function containing the probability of improvement (P I) and the normalized improvement (N I) to determine the sequence of heuristics. Considering that a certain strategy may have different performances in various optimization stages, we adopt a sliding window to emphasize the recent optimization information to the construction of the optimization sequence. To evaluate the performance of our proposal, we run EMSMO with 6 classic or advanced Evolutionary Algorithms (EAs) on CEC2017 benchmark functions with 30 independent trial runs and compare them fairly. The statistical results show that our proposed EMSMO is competitive with compared methods and has great potential to deal with continuous optimization problems.
  • Rui Zhong, Binan Tu, Enzhi Zhang, Masaharu Munetomo
    CEC 1 - 10 2023年
  • Rui Zhong, Enzhi Zhang, Masaharu Munetomo
    COMPLEX & INTELLIGENT SYSTEMS 2023年01月 
    Many optimization problems suffer from noise, and the noise combined with the large-scale attributes makes the problem complexity explode. Cooperative coevolution (CC) based on divide and conquer decomposes the problems and solves the sub-problems alternately, which is a popular framework for solving large-scale optimization problems (LSOPs). Many studies show that the CC framework is sensitive to decomposition, and the high-accuracy decomposition methods such as differential grouping (DG), DG2, and recursive DG (RDG) are extremely sensitive to sampling accuracy, which will fail to detect the interactions in noisy environments. Therefore, solving LSOPs in noisy environments based on the CC framework faces unprecedented challenges. In this paper, we propose a novel decomposition method named linkage measurement minimization (LMM). We regard the decomposition problem as a combinatorial optimization problem and design the linkage measurement function (LMF) based on Linkage Identification by non-linearity check for real-coded GA (LINC-R). A detailed theoretical analysis explains why our proposal can determine the interactions in noisy environments. In the optimization, we introduce an advanced optimizer named modified differential evolution with distance-based selection (MDE-DS), and the various mutation strategy and distance-based selection endow MDE-DS with strong anti-noise ability. Numerical experiments show that our proposal is competitive with the state-of-the-art decomposition methods in noisy environments, and the introduction of MDE-DS can accelerate the optimization in noisy environments significantly.
  • Daichi Morimoto, Motoaki Hiraga, Naoya Shiozaki, Kazuhiro Ohkura, Masaharu Munetomo
    Artificial Life and Robotics 27 4 751 - 760 2022年11月 
    This paper demonstrates to generate a collective behavior of a multi-legged robotic swarm based on the evolutionary robotics approach. Most studies in swarm robotics are conducted using mobile robots driven by wheels. This paper focuses on generating collective behavior using a multi-legged robotic swarm. The evolutionary robotics approach is employed for designing a robot controller. The intuition-based constraint factors are incorporated into the fitness function to make the gait of robots similar to natural organisms. The experiment on a task of forming a line is conducted in computer simulations using the PyBullet physics engine. The robot controller is represented by a recurrent neural network with a single hidden layer. The experimental results show that proposed constraint factors successfully designed the robot’s gait similar to natural organisms. The results also show that the evolutionary robotics approach successfully designed the robot controller for collective behavior of a multi-legged robotic swarm.
  • Daichi Morimoto, Motoaki Hiraga, Naoya Shiozaki, Kazuhiro Ohkura, Masaharu Munetomo
    ARTIFICIAL LIFE AND ROBOTICS 27 4 751 - 760 2022年11月 
    This paper demonstrates to generate a collective behavior of a multi-legged robotic swarm based on the evolutionary robotics approach. Most studies in swarm robotics are conducted using mobile robots driven by wheels. This paper focuses on generating collective behavior using a multi-legged robotic swarm. The evolutionary robotics approach is employed for designing a robot controller. The intuition-based constraint factors are incorporated into the fitness function to make the gait of robots similar to natural organisms. The experiment on a task of forming a line is conducted in computer simulations using the PyBullet physics engine. The robot controller is represented by a recurrent neural network with a single hidden layer. The experimental results show that proposed constraint factors successfully designed the robot's gait similar to natural organisms. The results also show that the evolutionary robotics approach successfully designed the robot controller for collective behavior of a multi-legged robotic swarm.
  • 能島, 裕介, 高木, 英行, 棟朝, 雅晴, 濱田, 直希, 西原, 慧, 高玉, 圭樹, 佐藤, 寛之, 桐淵, 大貴, 宮川, みなみ
    進化計算学会論文誌 13 1 1 - 9 進化計算学会 2022年07月13日 
    This paper is a report on Open Space Discussion (OSD) held in Evolutionary Computation Symposium 2021. The purpose of OSD is to share and discuss problems at hand and future research targets related to evolutionary computation. Discussion topics are voluntarily proposed by some of the participants, and other participants freely choose one to join in the discussion. Through free discussions based on the open space technology framework, it is expected that participants will have new research ideas and start some collaborations. This paper gives the concept of OSD and introduces six topics discussed this year. This paper also shows the responses to the questionnaire on OSD for future discussions, collaborations, and related events.
  • Daichi Morimoto, Motoaki Hiraga, Kazuhiro Ohkura, Masaharu Munetomo
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13491 LNCS 324 - 331 2022年 
    This paper focuses on generating and analyzing collective step-climbing behavior in a multi-legged robotic swarm. The multi-legged robotic swarm is expected to climb obstacles that are hard for a single robot by using other robots as stepping stones. However, designing a robot controller for a multi-legged robotic swarm becomes a challenging problem because it designs not only a gait for the basic movement of robots but also the behavior of robots to exhibit collective behavior. This paper employs the evolutionary robotics (ER) approach for designing a robot controller that consists of a recurrent neural network. The controllers are evaluated in the collective step-climbing task conducted by computer simulations. The results show that the ER approach successfully designed the robot gait to achieve the task. Additionally, the results of the analysis confirm that the robot obtained the actions to support other robots along with climbing other robots.
  • Enzhi Zhang, Mohamed Wahib, Masaharu Munetomo
    SCIS/ISIS 1 - 8 2022年
  • Courtney Powell, Katsunori Miura, Masaharu Munetomo
    SCIS/ISIS 1 - 8 2022年11月29日
  • Katsunori Miura, Courtney Powell, Masaharu Munetomo
    Soft Computing 26 19 10535 - 10546 2022年
  • Daichi Morimoto, Motoaki Hiraga, Naoya Shiozaki, Kazuhiro Ohkura, Masaharu Munetomo
    Artif. Life Robotics 27 2 333 - 340 2022年
  • Tadahiko Murata, Susumu Date, Yusuke Goto, Toshihiro Hanawa, Takuya Harada, Manabu Ichikawa, Hao Lee, Masaharu Munetomo, Akiyoshi Sugiki
    Proceedings - International Conference on Machine Learning and Cybernetics 2020-December 187 - 193 2020年12月02日 
    In this paper, we introduce a distribution system of synthesized data of Japanese population using Interdisciplinary Large-scale Information Infra-structures in Japan. Synthetic population is synthesized based on the statistics of the census that are conducted by the government and publicly released. Therefore, the synthesized data have no privacy data. However, it is easy to estimate the compositions of households, working status in a certain area from the synthetic population. Therefore, we currently distribute the synthesized data only for public or academic purposes. For academic purposes, it is important to encourage scholars or researchers to use a large-scale data of households, we define protection levels for the attributes in the synthetic populations. According to the protection levels, we distribute the data with proper attributes to those who try to use them. We encourage researchers to use the synthetic populations to be familiar to large-scale data processing.
  • Martin Schlueter, Mehdi Neshat, Mohamed Wahib, Masaharu Munetomo, Markus Wagner 0007
    CoRR abs/2010.07517 2020年
  • Martin Schlueter, Masaharu Munetomo
    AIP Conference Proceedings 2070 2019年02月12日 
    This contribution presents numerical results for global optimization of a multi-objective formulation of the well-known Cassini1 interplanetary space trajectory benchmark published by the European Space Agency (ESA). The original Cassini1 bench-mark is extended to four objectives and thus classified as many-objective problem. The MIDACO optimization software is used to solve the considered application in regard to two aspects. The first aspect considers the impact of massively parallelized co-evaluation in regard to reaching the global optimal solution and its influence on the solution objective space (particular the Pareto front shape). As a second aspect, the impact of a varying BALANCE parameter, which controls how much importance is given to each individual objective within a multi-objective preference scheme recently introduced as Utopia-Nadir-Balance, on the Pareto front shape is given. In regard to the first aspect, the results show that massive parallelization is an effective remedy to reduce the notoriously high number of sequential function evaluation while still maintaining a sufficient well distributed Pareto front. In regard to the second aspect, the results indicate that an exclusive focus on the first objective is preferable over a BALANCE parameter which distributes the preference over several objectives for this very special kind of application.
  • Tadahiko Murata, Takuya Harada, Manabu Ichika Wa, Yusuke Goto, Lee Hao, Susumu Date, Masaharu Munetomo, Akiyoshi Sugiki
    1 - 5 2019年 [査読有り][通常論文]
  • Courtney Powell, Katsunori Miura, Masaharu Munetomo
    Evolutionary Multi-Criterion Optimization - 10th International Conference, EMO 2019, East Lansing, MI, USA, March 10-13, 2019, Proceedings 683 - 694 Springer 2019年 [査読有り][通常論文]
  • Luca Faramondi, Gabriele Oliva, Stefano Panzieri, Federica Pascucci, Martin Schlueter, Masaharu Munetomo, Roberto Setola
    IEEE Trans. Syst. Man Cybern. Syst. 49 10 2036 - 2049 2019年 [査読有り][通常論文]
  • Martin Schlueter, Masaharu Munetomo
    IEEE Congress on Evolutionary Computation, CEC 2019, Wellington, New Zealand, June 10-13, 2019 912 - 919 2019年 [査読有り][通常論文]
  • Martin Schlueter, Masaharu Munetomo
    Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 306 - 307 ACM 2018年 [査読有り][通常論文]
  • Courtney Powell, Katsunori Miura, Masaharu Munetomo
    Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 298 - 299 ACM 2018年 [査読有り][通常論文]
  • Kousuke Izumiya, Masaharu Munetomo
    Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 179 - 180 ACM 2018年 [査読有り][通常論文]
  • Masaki Fujiwara, Masaharu Munetomo
    Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, Kyoto, Japan, July 15-19, 2018 41 - 42 ACM 2018年 [査読有り][通常論文]
  • Courtney Powell, Katsunori Miura, Masaharu Munetomo
    11th IEEE International Conference on Cloud Computing, CLOUD 2018, San Francisco, CA, USA, July 2-7, 2018 831 - 835 IEEE Computer Society 2018年 [査読有り][通常論文]
  • Katsunori Miura, Courtney Powell, Masaharu Munetomo
    2018 IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2018, Nicosia, Cyprus, December 10-13, 2018 137 - 144 IEEE Computer Society 2018年 [査読有り][通常論文]
  • Phyo Thandar Thant, Courtney Powell, Martin Schlueter, Masaharu Munetomo
    Proceedings - 2017 17th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2017 882 - 889 2017年07月10日 [査読有り][通常論文]
     
    Over the past decade, cloud computing has grown in popularity for the processing of scientific applications as a result of the scalability of the cloud and the ready availability of on-demand computing and storage resources. It is also a cost-effective alternative for scientific workflow executions with a pay-per-use paradigm. However, providing services with optimal performance at the lowest financial resource deployment cost is still challenging. Several fine-grained tasks are included in scientific workflow applications, and efficient execution of these tasks according to their processing dependency to minimize the overall makespan during workflow execution is an important research area. In this paper, a system for level-wise workflow makespan optimization and virtual machine deployment cost minimization for overall workflow optimization in cloud infrastructure is proposed. Further, balanced task clustering, to ensure load balancing in different virtual machine instances at each workflow level during workflow execution, is also considered. The system retrieves the necessary workflow information from a directed acyclic graph and uses the non-dominated sorting genetic algorithm II (NSGA-II) to carry out multiobjective optimization. Pareto front solutions obtained for makespan time and instance resource deployment cost for several scientific workflow applications verify the efficacy of our system.
  • Kousuke Izumiya, Masaharu Munetomo
    2017 IEEE Congress on Evolutionary Computation, CEC 2017 - Proceedings 905 - 912 2017年07月05日 [査読有り][通常論文]
     
    We propose a Decomposition-based Multi-objective Evolutionary Algorithm (MOEA/D) that incorporates a linkage identification technique to enhance the ability to solve difficult multi-objective optimization problems that have complex interactions among genes. Ensuring tight linkages is essential for genetic recombination operators to work effectively by preserving building blocks. For problems which are difficult to ensure tight linkages in encoding, the dependencies among loci have to be analyzed to identify the linkages for each building block. The proposed MOEA/D employs Linkage Identification with non-Monotonicity Detection (LIMD) to identify the linkages among pairs of loci by checking the non-monotonicity of fitness differences caused by pairwise perturbations for each scalar function in the MOEA/D. The results of numerical experiments conducted using a difficult multi-objective test function in which each building block is loosely encoded over the strings indicate that the proposed MOEA/D-LIMD outperforms the original MOEA/D and MOEA/D with tree-based graphical model (MOEA/D-GM).
  • Martin Schlueter, Masaharu Munetomo
    Journal of Artificial Intelligence and Soft Computing Research 7 3 171 - 181 2017年07月01日 [査読有り][通常論文]
     
    This contribution presents a numerical evaluation of the impact of parallelization on the performance of an evolutionary algorithm for mixed-integer nonlinear programming (MINLP). On a set of 200 MINLP benchmarks the performance of the MIDACO solver is assessed with gradually increasing parallelization factor from one to three hundred. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to CPU-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.
  • Phyo Thandar Thant, Courtney Powell, Martin Schlueter, Masaharu Munetomo
    SCIENTIFIC PROGRAMMING 2017年 [査読有り][通常論文]
     
    Cloud computing in the field of scientific applications such as scientific big data processing and big data analytics has become popular because of its service oriented model that provides a pool of abstracted, virtualized, dynamically scalable computing resources and services on demand over the Internet. However, resource selection to make the right choice of instances for a certain application of interest is a challenging problem for researchers. In addition, providing services with optimal performance at the lowest financial resource deployment cost based on users' resource selection is quite challenging for cloud service providers. Consequently, it is necessary to develop an optimization system that can provide benefits to both users and service providers. In this paper, we conduct scientific workflow optimization on three perspectives: makespan minimization, virtual machine deployment cost minimization, and virtual machine failure minimization in the cloud infrastructure in a level-wise manner. Further, balanced task assignment to the virtual machine instances at each level of the workflow is also considered. Finally, system efficiency verification is conducted through evaluation of the results with different multiobjective optimization algorithms such as SPEA2 and NSGA-II.
  • Martin Schlueter, Mohamed Wahib, Masaharu Munetomo
    APPLICATIONS OF EVOLUTIONARY COMPUTATION, EVOAPPLICATIONS 2017, PT I 10199 725 - 737 2017年 [査読有り][通常論文]
     
    The design and optimization of interplanetary space mission trajectories is known to be a difficult challenge. The trajectory of the Messenger mission (launched by NASA in 2004) is one of the most complex ones ever created. The European Space Agency (ESA) makes available a numerical optimization benchmark which resembles an accurate model of Messengers full mission trajectory. This contribution presents an optimization approach which is capable to (robustly) solve ESA's Messenger full mission benchmark to its putative global solution within 24 h run time on a moderate sized computer cluster. The considered algorithm, named MXHPC, is a parallelization framework for the MIDACO optimization algorithm which is an evolutionary method particularly suited for space trajectory design. The presented results demonstrate the effectiveness of evolutionary computing for complex real-world problems which have been previously considered intractable.
  • Phyo Thandar Thant, Courtney Powell, Akiyoshi Sugiki, Masaharu Munetomo
    2016 JOINT 8TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS (SCIS) AND 17TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS (ISIS) 293 - 298 2016年 [査読有り][通常論文]
     
    Hadoop configuration optimization is very challenging because of the complexity of its framework. And optimized Hadoop parameter configuration settings depend significantly on the performance of MapReduce applications in the cluster. Although much research has been conducted on Hadoop parameters configuration optimization, configuring its resource setting parameters to minimize the execution time of MapReduce jobs in clusters still needs a lot of continuing researches. Further, determining the type of machine instances that should be used to minimize the resource usage cost for executing applications in clusters is also difficult. This paper addresses these problems by optimizing the instance resource usage and execution time of MapReduce tasks using a multi-objective steady-state Non-dominated Sorting Genetic Algorithm II (ssNSGA-II) approach. In this approach, the instance resource usage cost of MapReduce tasks is calculated based on the cost of machine instance types and the number of machine instances in the Hadoop cluster. The optimized configuration is identified by selecting an optimal setting that satisfies two objective functions associated with instance resource usage and execution time minimization, from Pareto optimal front solutions. Although dynamic machine instance type is considered within the search process in our system, dynamic cluster size is out of consideration and intended to be carried out in our future. Experiments conducting using workloads from the HiBench benchmark on a high specification 6-node Hadoop cluster verify the efficacy of our proposed approach.
  • Courtney Powell, Masaharu Munetomo, Phyo Thandar Thant
    2016 JOINT 8TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS (SCIS) AND 17TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS (ISIS) 166 - 171 2016年 [査読有り][通常論文]
     
    In this study, we implemented three steady-state versions of NSGA-III that differ by the manner in which the offspring combined with the parent population is selected. These three schemes were then evaluated on the standard problem sets DTLZ1-4 in terms of four popular criteria: inverse generational distance (IGD), hypervolume (HV), convergence, and diversity. The results obtained suggest that utilizing a selection scheme in which the offspring is selected from the first non-dominated rank results in better solutions than other steady-state offspring selection schemes.
  • Katsunori Miura, Tazro Ohta, Courtney Powell, Masaharu Munetomo
    2016 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA) 2097 - 2102 2016年 [査読有り][通常論文]
     
    This paper proposes an intercloud brokerage method for system infrastructure deployments of genomic big data analytics workflows. The proposed method utilizes a conjunction of universally quantified atomic formula to describe requirements given by users, and selects combinations of cloud services based on logical reasoning by the replacement of definite clause sets created from conjunction of the atomic formulas, while preserving the declarative meaning of the system infrastructures' constraint conditions. We also define algorithms for the replacement of definite clause sets, and present an example of the use of the proposed intercloud brokerage method.
  • Katsunori Miura, Masaharu Munetomo
    2016 IEEE INTERNATIONAL CONFERENCE ON CLOUD ENGINEERING WORKSHOP (IC2EW) 172 - 177 2016年 [査読有り][通常論文]
     
    This paper proposes a formal predicate logic-based method for the specification of intercloud information systems comprising combinations of cloud services. The proposed framework utilizes predicates with variables in universally quantified atoms to provide general descriptive capability for a wide variety of cloud services and their various properties. We define the proposed Predicate Logic-defined Specification (PLS) method and explain how it can be applied to describe three-tier web applications using an example global-scale intercloud environment. We also discuss the effectiveness of the proposed method in Cloud Service Brokerage (CSB) scenarios compared with conventional approaches based on Satisfiability problems (SAT) and Satisfiability Modulo Theories (SMT).
  • Takahito Seyama, Masaharu Munetomo
    2016 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 846 - 852 2016年 [査読有り][通常論文]
     
    This paper proposes a 3D modeling system that uses multi-player interactive genetic algorithm (MiGA) to simplify the 3D modeling process for ordinary persons who wish to model pairs of glasses. The proposed system has three advantages: First, users are able to create 3D models via simple operations such as evaluation of 3D models. Second, this system reduces user fatigue by showing the information searched for and utilized by similar users, discovered by collaborative filtering. Third, this system also facilitates collaboration among a large number of users by employing Platform as-a Service (PaaS) and NoSQL database for scalability. The results of real and pseudo user experiments conducted verify the efficacy of the proposed system.
  • Martin Schlueter, Masaharu Munetomo
    2016 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 830 - 837 2016年 [査読有り][通常論文]
     
    This contribution addresses the question if and how the impact of parallelization can influence the performance of an evolutionary algorithm on constrained mixed-integer nonlinear optimization problems. On a set of 200 MINLP benchmarks the performance of the MIDACO solver is numerically assessed with gradually increasing parallelization factor from 1 to 100. The results demonstrate that the efficiency of the algorithm can be significantly improved by parallelized function evaluation. Furthermore, the results indicate that the scale-up behaviour on the efficiency resembles a linear nature, which implies that this approach will even be promising for very large parallelization factors. The presented research is especially relevant to cpu-time consuming real-world applications, where only a low number of serial processed function evaluation can be calculated in reasonable time.
  • Shintaro Mikuni, Kota Kodama, Akira Sasaki, Naoki Kohira, Hideki Maki, Masaharu Munetomo, Katsumi Maenaka, Masataka Kinjo
    PLOS ONE 10 7 e0130933  2015年07月 [査読有り][通常論文]
     
    FtsZ is an attractive target for antibiotic research because it is an essential bacterial cell division protein that polymerizes in a GTP-dependent manner. To find the seed chemical structure, we established a high-throughput, quantitative screening method combining fluorescence cross-correlation spectroscopy (FCCS) and surface plasmon resonance (SPR). As a new concept for the application of FCCS to polymerization-prone protein, Staphylococcus aureus FtsZ was fragmented into the N-terminal and C-terminal, which were fused with GFP and mCherry (red fluorescent protein), respectively. By this fragmentation, the GTP-dependent head-to-tail dimerization of each fluorescent labeled fragment of FtsZ could be observed, and the inhibitory processes of chemicals could be monitored by FCCS. In the first round of screening by FCCS, 28 candidates were quantitatively and statistically selected from 495 chemicals determined by in silico screening. Subsequently, in the second round of screening by FCCS, 71 candidates were also chosen from 888 chemicals selected via an in silico structural similarity search of the chemicals screened in the first round of screening. Moreover, the dissociation constants between the highest inhibitory chemicals and Staphylococcus aureus FtsZ were determined by SPR. Finally, by measuring the minimum inhibitory concentration, it was confirmed that the screened chemical had antibacterial activity against Staphylococcus aureus, including methicillin-resistant Staphylococcus aureus (MRSA).
  • Masataka Mizukoshi, Masaharu Munetomo
    2015 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 1575 - 1580 2015年 [査読有り][通常論文]
     
    DDoS attacks become serious as one of the menaces of the Internet security. It is difficult to prevent because DDoS attacker send spoofing packets to victim which makes the identification of the origin of attacks very difficult. A series of techniques have been studied such as pattern matching by learning the attack pattern and abnormal traffic detection. However, pattern matching approach is not reliable because attackers always set attacks of different traffic patterns and pattern matching approach only learns from the past DDoS data. Therefore, a reliable system has to watch what kind of attacks are carried out now and investigate how to prevent those attacks. Moreover, the amount of traffic flowing through the Internet increase rapidly and thus packet analysis should be done within considerable amount of time. This paper proposes a scalable, real-time traffic pattern analysis based on genetic algorithm to detect and prevent DDoS attacks on Hadoop distributed processing infrastructure. Experimental results demonstrate the effectiveness of our scalable DDoS protection system.
  • 合田 憲人, 山地 一禎, 中村 素典, 横山 重俊, 吉岡 信和, 政谷 好伸, 西村 浩二, 棟朝 雅晴
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 114 236 1 - 5 一般社団法人電子情報通信学会 2014年10月07日 [査読無し][通常論文]
  • Ryosuke Hasebe, Rina Kouda, Kei Ohnishi, Masaharu Munetomo
    2014 JOINT 7TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS (SCIS) AND 15TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS (ISIS) 1327 - 1332 2014年 [査読無し][通常論文]
     
    A variety of data are accumulated in the Internet and the data are increasing in amount everyday, for example, open data provided by governments of multiple countries. Utilizing such data might be linked to creating new businesses or services. Therefore, it would be useful if we have a system that helps users discuss purposes to utilize the data quickly and efficiently. So, we conceptually present a system implementing a human-based genetic algorithm that is intended to help users discuss purposes to utilize the data quickly and efficiently, and then develop a web-based system for discussing suitable tags for given images according to the concept. We also conduct subjective tests for evaluating the developed system. The results do not show statistical significant difference between the developed system and a conventional way, but we obtain several positive comments about the usability of the developed system.
  • Courtney Powell, Takashi Aizawa, Masaharu Munetomo
    2014 IEEE 3RD INTERNATIONAL CONFERENCE ON CLOUD NETWORKING (CLOUDNET) 102 - 107 2014年 [査読有り][通常論文]
     
    This paper outlines the design of an authentication infrastructure for linking distributed heterogeneous cloud systems managed by different cloud management middleware to enable them to interoperate as an integrated inter-cloud system. This authentication infrastructure achieves single sign-on (SSO), which allows users to log in once and access the various cloud systems without being asked to log in again at each system. Further, it does so without changing the design of the existing cloud systems by using a proxy certificate repository and Shibboleth authentication technology. We also report on a prototype implementation of the system that validates the design of the authentication infrastructure.
  • Martin Schlueter, Masaharu Munetomo
    2014 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 832 - 839 2014年 [査読有り][通常論文]
     
    The impact of parallelization on the optimization process of space mission trajectories is investigated in this contribution. As space mission trajectory reference model, the well known Cassini1 benchmark, published by the European Space Agency (ESA), is considered and solved here with the MIDACO optimization software. It can be shown that significant speed ups can be gained by applying parallelization.
  • Omar Arif Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama
    INFORMATION SCIENCES 233 54 - 86 2013年06月 [査読有り][通常論文]
     
    Real parameter constrained problems are an important class of optimization problems that are encountered frequently in a variety of real world problems. On one hand, Genetic Algorithms (GAs) are an efficient search metaheuristic and a prominent member within the family of Evolutionary Algorithms (EAs), which have been applied successfully to global optimization problems. However, genetic operators in their standard forms are blind to the presence of constraints. Thus, the extension of GAs to constrained optimization problems by incorporating suitable handing techniques is an active direction within GAs research. Recently, we have proposed a Binary Real coded Genetic Algorithm (BRGA). BRGA is a new hybrid approach that combines cooperative Binary coded GA (BGA) with Real coded GA (RGA). It employs an adaptive parameter-based hybrid scheme that distributes the computational power and regulates the interactions between the cooperative versions, which operate in a sequential time-interleaving manner. In this study, we aim to extend BRGA to constrained problems by introducing a modified dynamic penalty function into the architecture of BRGA. We use the CEC'2010 benchmark suite of 18 functions to analyze the quality, time and scalability performance of BRGA. To investigate the effectiveness of the proposed modification, we compare the performance of BRGA under both the original and the modified penalty functions. Moreover, to demonstrate the performance of BRGA, we compare it with the performance of some other EAs from the literature. We also implement a robust parameter tuning procedure that relies on techniques from statistical testing, experimental design and Response Surface Methodology (RSM) to estimate the optimal values for the control parameters to secure a good performance by BRGA against specific problems at hand. (c) 2013 Elsevier Inc. All rights reserved.
  • Martin Schlueter, Masaharu Munetomo
    2013 IEEE Congress on Evolutionary Computation, CEC 2013 635 - 641 2013年 [査読有り][通常論文]
     
    Two different parallelization strategies for evolutionary algorithms for mixed integer nonlinear programming (MINLP) are discussed and numerically compared in this contribution. The first strategy is to parallelize some internal parts of the evolutionary algorithm. The second strategy is to parallelize the MINLP function calls outside and independently of the evolutionary algorithm. The first strategy is represented here by a genetic algorithm (arGA) for numerical testing. The second strategy is represented by an ant colony optimization algorithm (MIDACO) for numerical testing. It can be shown that the first parallelization strategy represented by arGA is inferior to the serial version of MIDACO, even though if massive parallelization via GPGPU is used. In contrast to this, theoretical and practial tests demonstrate that the parallelization strategy of MIDACO is promising for cpu-time expensive MINLP problems, which often arise in real world applications. © 2013 IEEE.
  • Courtney Powell, Masaharu Munetomo, Martin Schlueter, Masataka Mizukoshi
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8211 427 - 438 2013年 [査読有り][通常論文]
     
    A new wearable computing era featuring devices such as Google Glass, smartwatches, and digital contact lenses is almost upon us, bringing with it usability issues that conventional human computer interaction (HCI) modalities cannot resolve. Brain computer interface (BCI) technology is also rapidly advancing and is now at a point where noninvasive BCIs are being used in games and in healthcare. Thought control of wearable devices is an intriguing vision and would facilitate more intuitive HCI however, to achieve even a modicum of control BCI currently requires massive processing power that is not available on mobile devices. Cloud computing is a maturing paradigm in which elastic computing power is provided on demand over networks. In this paper, we review the three technologies and take a look at possible ways cloud computing can be harnessed to provide the computational power needed to facilitate practical thought control of next-generation wearable computing devices. © Springer International Publishing 2013.
  • Masaharu Munetomo, Shintaro Bando
    Proceedings - 2013 IEEE International Conference on Big Data, Big Data 2013 28  2013年 [査読有り][通常論文]
     
    This paper proposes a scalable framework to process and evolve services online adaptively from big data obtained from their users employing interactive evolutionary computation realized on a scalable infrastructure as platform as a service. Instead of collecting/storing/processing/analyzing big data to improve services offline, the proposed framework enables us to evolve and optimize adaptively every when collecting data from users interactively. © 2013 IEEE.
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    Natural Computing Series 46 83 - 104 2013年 [査読有り][通常論文]
     
    In this chapter,we propose a newapproach to solve the most general form of global optimization problems, namely, non-convex Mixed-Integer Nonlinear Programming (MINLP) and non-convex Nonlinear Programming (NLP) problems. The target is to solve MINLP/NLP problems from different domains of research in fewer fitness evaluations as compared to other state-of-the-art stochastic algorithms in the area. The algorithm is GPU compatible and shows remarkable speedups over nVidia’s CUDA-compatible GPUs. MINLP problems involve both discrete and continuous variables with several active nonlinear equality and inequality constraints making them extremely difficult to solve. The proposed algorithm is named the adaptive resolution Genetic Algorithm (arGA) as it exploits the concept of controlling the search space size and resolution in an adaptive manner. Using entropy measures, the proposed algorithm adaptively controls the intensity of the genetic search in a given sub-solution space, i.e., promising regions are searched more intensively as compared to other regions. The algorithm is equipped with an asynchronous adaptive local search operator to further improve the performance. Niching is incorporated by using a technique inspired from the Tabu search. The algorithm reduces the chances of convergence to local optima by maintaining a list of already visited optima and penalizing their neighborhoods. The proposed technique was able to find the best-known solutions to extremely difficult MINLP/NLP problems in fewer fitness evaluations and in a competitive amount of time. The results section discusses the performance of the algorithm and the effect of different operators by using a variety ofMINLP/NLPs from different problem domains. GPU implementation shows a speedup of up to 42× for single precision and 20× for double precision implementation over the nVidia C2050 GPU architecture.
  • Courtney Powell, Masaharu Munetomo, Attia Wahib, Takashi Aizawa
    Proceedings - 2013 IEEE/ACM 6th International Conference on Utility and Cloud Computing, UCC 2013 458 - 463 2013年 [査読有り][通常論文]
     
    The aim of the simple heterogeneous inter-cloud manager (SHINCLOM) project is to develop a prototype web-based single sign-on inter-cloud management portal that gives users the ability to easily configure and launch inter-cloud VPCs, HPC clusters, and autonomic applications and services. We employ a model-based approach in which the various requirements of the project are mapped to the layers of a proposed autonomic model and implemented using free open source software (FOSS). In this paper, we outline the requirements of the project, discuss our overall construction methodology, and give an overview of the sections implemented to date. © 2013 IEEE.
  • 合田 憲人, 東田 学, 坂根 栄作, 天野 浩文, 小林 克志, 棟朝 雅晴, 江川 隆輔, 建部 修見, 鴨志田 良和, 滝澤 真一朗, 永井 亨, 岩下 武史, 石川 裕
    先進的計算基盤システムシンポジウム論文集 5 2012 227 - 236 一般社団法人情報処理学会 2012年05月09日 [査読無し][通常論文]
     
    本稿では,現在文部科学省により整備が進められている革新的ハイパフォーマンス・コンピューティング・インフラ (HPCI) のための認証基盤の設計について述べる.本認証基盤では,グリッド上の認証技術である Grid Security Infrastructure (GSI),および認証連携技術である Shibboleth を用いることにより, HPCI を構成する計算機や共用ストレージに対するシングルサインオンを実現する.本稿ではまた,本認証基盤の設計を検証するために構築した実験環境上での実証実験についても報告する.
  • Wahib Mohamed, Munawar Asim, Munetomo Masaharu
    情報処理学会論文誌 論文誌トランザクション 2011 2 7 - 17 情報処理学会 2012年04月 [査読無し][通常論文]
  • 棟朝 雅晴, 染谷 博司
    電気学会誌 = The journal of the Institute of Electrical Engineers of Japan 132 4 204 - 207 一般社団法人 電気学会 2012年04月01日 [査読無し][通常論文]
     
    本記事に「抄録」はありません。
  • 中小規模大学におけるクラウド利用の取り組みと広域分散クラウドへの期待
    柏崎 礼生, 棟朝 雅晴, 髙井 昌彰
    Proceedings of NORTH Internet Symposium 2012 18 101 - 108 2012年02月 [査読有り][通常論文]
  • Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama
    2012 21ST INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS (ICCCN) 1 - 9 2012年 [査読有り][通常論文]
     
    Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological impact. On the other hand, virtualization adds a greater flexibility to the resource managers in addressing such challenges. However, at the same time, it imposes a further challenge of added management complexity. Recently, we have proposed a resource management model for cloud platforms, which utilizes a new resource mapping formulation and relays on a hybrid virtualization framework in an attempt to realize a resource manager that intelligently adapts the available cloud resources to satisfy the conflicting objectives of the running applications and underlying infrastructures' requirements. Moreover, we have proposed state of the art Binary-Real coded Genetic Algorithm (BRGA), which has been applied successfully to a wide spectrum of global and constrained optimization problems from the known benchmark suites. In this paper, we aim to proceed by proposing a mathematical model and a modified version of BRGA to validate our model. In addition, we aim to evaluate the feasibility, effectiveness and scalability of our approach through simulation experiments.
  • 堀 伸哉, 棟朝 雅晴, 赤間 清
    進化計算学会論文誌 3 2 63 - 72 進化計算学会 2012年 [査読有り][通常論文]
     
    This paper proposes a new method of Estimation Distribution Algorithm (EDA) named Bayesian Optimization Algorithm with Mixture Distribution (BOA-MD) that employs mixture of multiple Bayesian Networks to solve complex problems. In order to solve complex problems that are modeled by multiple Bayesian networks with hidden variables, the original BOA needs a large computation cost to model multiple probabilistic structures as a large, complex Bayesian network.The BOA-MD tries to build multiple models of Bayesian networks considering hidden variables with Expectation Maximization (EM) method to express all the structures of probabilistic distribution.The mixture of Bayesian networks is composed of a hidden variable C and some Bayesian Networks. Each composed Bayesian network can express each problem structure of multiple distributions. We perform numerical experiments by two test functions: Cross-Trap function and Triple-Trap function. These two test functions are to represent problems with multiple distributions. BOA-MD can solve these test problems with smaller number of fitness evaluations and larger modeling overheads than those by BOA for Cross-Trap5 function. This is because BOA-MD needs large computation time to construct Mixture of Bayesian Network. The BOA-MD can solve the problem faster than the original BOA when the overhands of each fitness evaluation becomes larger. At Triple-Trap function, BOA-MD can detect better solution than BOA.
  • Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama
    2012 21ST INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS (ICCCN) 2012年 [査読有り][通常論文]
     
    Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological impact. On the other hand, virtualization adds a greater flexibility to the resource managers in addressing such challenges. However, at the same time, it imposes a further challenge of added management complexity. Recently, we have proposed a resource management model for cloud platforms, which utilizes a new resource mapping formulation and relays on a hybrid virtualization framework in an attempt to realize a resource manager that intelligently adapts the available cloud resources to satisfy the conflicting objectives of the running applications and underlying infrastructures' requirements. Moreover, we have proposed state of the art Binary-Real coded Genetic Algorithm (BRGA), which has been applied successfully to a wide spectrum of global and constrained optimization problems from the known benchmark suites. In this paper, we aim to proceed by proposing a mathematical model and a modified version of BRGA to validate our model. In addition, we aim to evaluate the feasibility, effectiveness and scalability of our approach through simulation experiments.
  • 棟朝雅晴, 染谷博司
    電気学会誌 132 4 204 - 207 2012年 [査読無し][通常論文]
  • Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    IPSJ Transactions on Bioinformatics 5 7 - 17 2012年 [査読有り][通常論文]
     
    De Novo ligand design is an automatic fragment-based design of molecules within a protein binding site of a known structure. A Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, is introduced to join predocked fragments with a user-supplied list of fragments. A novel feature proposed is the simultaneous optimization of force field energy and a term enforcing 3D-overlap to known binding mode(s). The performance of the algorithm is tested on Liver X receptors (LXRs) using a library of about 14,000 fragments and the binding mode of a known heterocyclic phenyl acetic acid to bias the design. We further introduce the use of GPU (Graphics Processing Unit) to overcome the excessive time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragment sets and target receptors for more complex instances. The results show how the nVidia's Tesla C2050 GPU was utilized to enable the generation of complex agonists effectively. In fact, eight of the 1,809 molecules designed for LXRs are found in the ZINC database of commercially available compounds.
  • 中井 真五, 小原 伸哉, 田中 英一, 今野 大輔, 棟朝 雅晴
    環境工学総合シンポジウム講演論文集 2012 0 277 - 278 一般社団法人 日本機械学会 2012年 [査読無し][通常論文]
     
    It is thought that plants have evolved to modulate the amount of light received by the leaves in order to competition for survival. Investigation of a plant shoot configuration is used to obtain valuable information concerning the received light system. As an example, it is thought that the leaves of various shape has a role important about die received light characteristics of the plant individual. In this research, we performed a numerical experiment that simulates the plant shoot by using a genetic algorithm analysis program in order to investigate the received light characteristics of a plant shoot. As a result, the relation between the placement of plant shoot of various shapes and the light-receiving amount is clarified.
  • Eiichi Tanaka, Shin'ya Obara, Shingo Nakai, Daisuke Konno, Masaharu Munetomo
    2012 15TH INTERNATIONAL CONFERENCE ON ELECTRICAL MACHINES AND SYSTEMS (ICEMS 2012) 2012年 [査読無し][通常論文]
     
    Investigation of a whole plant configuration is used to obtain valuable information concerning the received light system. As an example, it is thought that branching of a plant has an important role about light receiving properties of the individual. In this research, development of the analysis program by simulating branch of a plant using L-system was tried, because numerical value experiments on light receiving properties of the plant. From these results, the relations of the analysis program applied to investigate branching of the plant shoot and the light received quantity was developed.
  • 棟朝雅晴, 高井昌彰
    情報科学技術フォーラム FIT 2011 15-18  2011年08月22日 [査読無し][通常論文]
  • Mohamed Wahi, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    Proceedings - 2011 IEEE World Congress on Services, SERVICES 2011 265 - 271 2011年 [査読有り][通常論文]
     
    Cloud computing is impacting the modern Internet computing and businesses in every aspect. One feature of clouds is the convenience of using the services offered by the cloud. Consequently, most cloud service providers use WS for users and developers to interface with the cloud. However, the current cloud WS are focused into core and fundamental modern computing functionalities. We anticipate as cloud developments tools mature and cloud applications become more popular, there will be an opportunity for designing and implementing applications/services to be embedded in the cloud for use by applications in the cloud. We propose a framework for WS deployment in the cloud to be usable by applications residing in the same cloud. The framework capitalizes on the cloud strong points to offer a higher value to the service consumer inside the cloud. The authoritative nature of clouds would enable more efficient models for WS publishing, indexing and description. Moreover, being hosted in the cloud, WS can build on the high scalability offered by the cloud with a much higher reliability. Finally, scheduling the instances using the WS in bundle with the WS instances could offer a LAN-like connectivity performance driving down the latency to the magnitude of lower microseconds. In this paper, we highlight the challenges and opportunities of cloud applications using cloud embedded Web services. We give a description of the different aspects by illustrating the different components, together with an end-to-end use case to show the applicability of the proposed system. © 2011 IEEE.
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6683 203 - 217 2011年 [査読有り][通常論文]
     
    Non convex mixed integer non-linear programming problems (MINLPs) are the most general form of global optimization problems. Such problems involve both discrete and continuous variables with several active non-linear equality and inequality constraints. In this paper, a new approach for solving MINLPs is presented using adaptive resolution based micro genetic algorithms with local search. Niching is incorporated in the algorithm by using a technique inspired from the tabu search algorithm. The proposed algorithm adaptively controls the intensity of the genetic search in a given sub-solution space, i.e. promising regions are searched more intensely as compared to other regions. The algorithm reduces the chances of convergence to a local minimum by maintaining a list of already visited minima and penalizing their neighborhoods. This technique is inspired from the tabu list strategy used in the tabu search algorithm. The proposed technique was able to find the best-known solutions to extremely difficult MINLP/NLP problems in a competitive amount of time. The results section discusses the performance of the algorithm and the effect of different operators by using a variety of MINLP/NLPs from different problem domains. © Springer-Verlag Berlin Heidelberg 2011.
  • Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    2011 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 803 - 811 2011年 [査読有り][通常論文]
     
    Led by General Purpose computing over Graphical Processing Units (GPGPUs), the parallel computing area is witnessing a rapid change in dominant parallel systems. A major hurdle in this switch is the Single Instruction Multiple Thread (SIMT) architecture of GPUs which is usually not suitable for the design of legacy parallel algorithms. Genetic Algorithms (GAs) is no exception for that. GAs are commonly parallelized due to the high demanding computational needs. Given the performance of GPGPUs, the need to best exploit them to maximize computing efficiency for parallel GAs is demandingly growing. The goal of this paper is to shed light on the challenges parallel GAs designers/programmers will likely face while trying to achieve this, and to provide some practical advice on how to maximize GPGPU exploitation as a result. To that end, this paper provides a study on adapting legacy parallel GAs on GPGPU systems. The paper exposes the design challenges of nVidia's GPU architecture to the parallel GAs community by: discussing features of GPU, reviewing design issues in GPU relevant to parallel GAs, the design and introduction of new techniques to achieve an efficient implementation for parallel GAs and observing the effect of the pivotal points that both capitalize on the strengths of GPU and limit the deficiencies/overheads of GPUs. The paper demonstrates the performance of designed-for-GPGPU parallel GAs representing the entire spectrum of legacy parallel model of GAs over nVidia Tesla C1060 workstation showing a significant improvement in performance after optimizing and tuning the algorithms for GPU.
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    2011 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 318 - 325 2011年 [査読有り][通常論文]
     
    In this paper we propose a many-core implementation of evolutionary computation for GPGPU (General-Purpose Graphic Processing Unit) to solve non-convex Mixed Integer Non-Linear Programming (MINLP) and non-convex Non Linear Programming (NLP) problems using a stochastic algorithm. Stochastic algorithms being random in their behavior are difficult to implement over GPU like architectures. In this paper we not only succeed in implementation of a stochastic algorithm over GPU but show considerable speedups over CPU implementations. The stochastic algorithm considered for this paper is an adaptive resolution approach to genetic algorithm (arGA), developed by the authors of this paper. The technique uses the entropy measure of each variable to adjust the intensity of the genetic search around promising individuals. Performance is further improved by hybridization with adaptive resolution local search (arLS) operator. In this paper, we describe the challenges and design choices involved in parallelization of this algorithm to solve complex MINLPs over a commodity GPU using Compute Unified Device Architecture (CUDA) programming model. Results section shows several numerical tests and performance measurements obtained by running the algorithm over an nVidia Fermi GPU. We show that for difficult problems we can obtain a speedup of up to 20x with double precision and up to 42x with single precision.
  • Masaharu Munetomo
    2011 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 312 - 317 2011年 [査読有り][通常論文]
     
    Future trend of supercomputing goes toward exa flops, which is realized by millions of cores expected to be installed on around 2018. Such massive parallelism makes programming difficult. Inherent parallel nature of evolutionary computation is a promising factor in designing optimization algorithms that adapt to such massively parallel architecture although there are some problems to be solved to realize robust algorithm that can analyze complex interactions among genes. This paper discusses current status and future trend in realizing robust and scalable evolutionary computation on such extreme-scale supercomputers.
  • Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama
    Proceedings - 2011 IEEE 4th International Conference on Cloud Computing, CLOUD 2011 754 - 755 2011年 [査読有り][通常論文]
     
    Resource management in cloud platforms becomes an increasingly complex and daunting task surrounded by various challenges of stringent QoS requirements, service availability guaranteeing and escalating overhead of the infrastructure that resulted from operation costs and ecological effects. Virtualization adds a greater flexibility to the resource manager in addressing such challenges. However, it imposes a further challenge of added management complexity. So, in this brief paper, we attempt to address still an open question of how to employ virtualization techniques effectively to realize a resource manager that intelligently adapts cloud platforms resource usage to satisfy the conflicting objectives of running applications and underlying cloud infrastructures by proposing a novel multi-level architecture which relays on a hybrid virtualization framework. We describe its functional components and dataflow and highlight the next steps that we will adopt in order to realize it and evaluate its feasibility and effectiveness. © 2011 IEEE.
  • 北海道大学アカデミッククラウドにおけるコンテンツマネジメントシステムの展開
    情報処理学会第10回情報科学技術フォーラム論文集(査読付論文) RL-004  2011年 [査読無し][通常論文]
  • A Framework for Problem-Specific QoS Based Scheduling in Grids
    Advances in Grid Computing 19 - 28 2011年 [査読無し][通常論文]
  • Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama
    Proceedings of the 2011 3rd World Congress on Nature and Biologically Inspired Computing, NaBIC 2011 149 - 156 2011年 [査読無し][通常論文]
     
    Genetic algorithms (GAs) are vital members within the family biologically inspired algorithms. It has been proven that the performance of GAs is largely affected by the type of encoding schemes used to encode optimization problems. Binary and real encoding schemes are the most popular ones. However, it is still controversial to decide the superiority of one of them for GAs performance. Therefore, we have recently proposed binary-real coded GA (BRGA) that has the ability to use both encoding schemes at the same time. BRGA relays on a parameterized hybrid scheme to share the computational power and coordinate the cooperation between binary coded GA (BGA) and real coded GA (RGA). In this paper, we aim to evaluate the performance of BRGA systematically by utilizing CEC'2005 benchmark of 25 problems and adopting a robust experimental analysis approach. The quality and time performance of BRGA against the benchmark suite and in comparison with original component algorithms (BGA and RGA) is reported discussed and analyzed. Moreover, the performance of BRGA is compared with other Evolutionary Algorithms (EAs) from the literature. © 2011 IEEE.
  • Abdul-Rahman Omar Arif, Munetomo Masaharu, Akama Kiyoshi
    Artificial Life and Robotics 16 1 121 - 124 Springer 2011年 [査読無し][通常論文]
     
    In genetic algorithms (GAs), is it better to use binary encoding schemes or floating point encoding schemes? In this article, we try to tackle this controversial question by proposing a novel algorithm that divides the computational power between two cooperative versions of GAs. These are a binary-coded GA (bGA) and a real-coded GA (rGA). The evolutionary search is primarily led by the bGA, which identifi es promising regions in the search space, while the rGA increases the quality of the solutions obtained by conducting an exhaustive search throughout these regions. The resolution factor (R), which has a value that is increasingly adapted during the search, controls the interactions between the two versions. We conducted comparison experiments employing a typical benchmark function to prove the feasibility of the algorithm under the critical scenarios of increasing problem dimensions and decreasing precision power.
  • Munawar Asim, Wahib Mohamed, Munetomo Masaharu, Akama Kiyoshi
    Future Generation Computer Systems 26 4 633 - 644 ELSEVIER 2010年04月 [査読無し][通常論文]
     
    We present GridUFO (Grid based Unified Framework for Optimization), a Service Oriented Architecture (SOA) compliant Problem Solving Environment (PSE) that allows the user to implement/share metaheuristics based optimization algorithms over a Grid. GridUFO eradicates the shortcomings of earlier projects and provides a unified approach for using algorithm/problem pair over a Grid in the easiest possible "plug & play" manner. This framework allows the users to concentrate on the actual application development, by hiding all the complexities involved in a Grid, without compromising on the functionality and flexibility promised by a Grid. This paper provides a detailed overview of the GridUFO infrastructure, specifically the way it deals with optimization algorithms and objective functions, handles Service Level Agreements (SLAs), and follows SOA. We also present various results achieved, that demonstrate both the utility and performance of GridUFO under various application workloads and scenarios.
  • Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2010, Las Vegas, Nevada, USA, July 12-15, 2010, 2 Volumes 658 - 664 CSREA Press 2010年 [査読有り][通常論文]
  • Masafumi Kuroda, Kunihito Yamamori, Masaharu Munetomo, Moritoshi Yasunaga, Ikuo Yoshihara
    2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 1 - 6 2010年 [査読有り][通常論文]
     
    This paper proposes a novel crossover operator for solving large-scale traveling salesman problems (TSPs) by using a Hybrid Genetic Algorithm (HGA) with Lin-Kernighan heuristic for local search and we tentatively name Zoning Crossover (Z-Cross). The outline of Z-Cross is firstly to set a zone in the travelling area according to some rules, secondly to cut edges connecting cities between inside and outside the zone, thirdly to exchange edges inside the zone of one parent and those of the other parent, and lastly to reconnect sub-tours and isolated cities, which come about in the 3rd step mentioned above, so as to construct a new tour of TSP. The method is compared with conventional three crossovers; those are the Maximal Preservative Crossover, the Greedy Sub-tour Crossover and the Edge Recombination Crossover, and evaluated from the viewpoints of tour quality and CPU time. Ten benchmarks are selected from the well-known TSP website of Georgia Institute of Technology, whose names are xqf131, xqg237, ..., sra104815. The experiments are performed ten times for each crossover and each benchmark and show that the Z-Cross succeeds in finding better solution and running faster than the conventional methods. Six benchmarks with size from 39,603 to 104,815 cities are selected from the TSP website and challenged the records of tour lengths. The Z-Cross betters the record of the problem rbz43748 and approaches to solutions less than only 0.02% over the known best solutions for five instances.
  • Omar Abdul-Rahman, Masaharu Munetomo, Kiyoshi Akama
    PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON CLOUD COMPUTING, GRIDS, AND VIRTUALIZATION (CLOUD COMPUTING 2010) 32 - 40 2010年 [査読無し][通常論文]
     
    Virtualization is a technology originally developed for mainframe computing. However, recent developments in the virtualization makes it a key technology to address the problems of modern distributed infrastructure like cloud platforms. Perhaps, one of the most important mechanisms provided by virtualization is the ability to migrate running applications without affecting the end user in a seamless manner. So, virtual machine migration is a promising approach to realize the objectives of efficient, adaptive and dynamic resource manager for virtualized environments. In this the paper, we present the state of art migration based resource managers for virtualized environments, compare and discuss different types of the underlying management algorithms from algorithmic issues standpoint.
  • Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    2010 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC) 17 - 24 2010年 [査読無し][通常論文]
     
    A principal fragment-based design approach is De Novo ligand design at which small-molecule structures from a database of existing compounds (or compounds that could be made) are docked into the protein binding site following a virtual synthesis scheme. New virtual structures can easily be constructed from combinatorial building blocks. Typically, tens of thousands of orientations are generated for each ligand candidate, therefore global optimization algorithms are usually employed to search the chemical space by generating new molecular structures through probing many different fragments in a combinatorial fashion. We propose using Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, in searching the combination of pre-docked fragments through minimizing the energy of ligand-receptor docking. We further introduce the use of GPU (Graphical Processing Unit) to overcome the very long time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragments and target receptors for more complex instances. The experiments resulted in regenerating three drug-like compounds defined in the ZINC database as well as finding a new compound. The Results show how the nVidia's Tesla C1060 GPU was utilized to accelerate the docking process by two orders of magnitude.
  • Development of a Novel Crossover of Hybrid Genetic Algorithms for Large-scale Traveling Salesman Problems
    Proceedings of the Fifteenth International Symposium on Artificial Life and Robotics 2010 828 - 831 2010年 [査読無し][通常論文]
  • Munawar Asim, Wahib Mohamed, Munetomo Masaharu, Akama Kiyoshi
    International Journal of Advancements in Computing Technology 1 2 16 - 28 Advanced Institute of Convergence IT 2009年12月 [査読無し][通常論文]
     
    This paper presents a case study to illustrate the design and implementation of cellular Genetic Algorithm (cGA) with Local Search (LS) to solve Capacitated Vehicle Routing Problem (CVRP) over Cell Broadband Engine (Cell BE). Cell BE is a heterogeneous, distributed memory multicore processor architecture for multimedia applications with regular memory access requirements. It has one 64-bit Power Processing Element (PPE) that acts as the main processor and 8 Synergistic Processing Elements (SPEs) with only 256 KB of local memory, each for instructions and data. GAs on the other hand use popu...
  • Munetomo Masaharu, Akama Kiyoshi, Maeda Haruki
    WSEAS Transactions on Information Science and Applications 6 5 788 - 797 World Scientific and Engineering Academy and Society 2009年05月 [査読無し][通常論文]
     
    Ligand docking checks whether a drug chemical called ligand matches the target receptor protein of human organ or not. Docking by computer simulation is becoming popular in drug design process to reduce cost and time of the chemical experiments. This paper presents a novel approach generating optimal ligand structures from scratch based on de novo ligand design approach employing Bayesian optimization algorithm to realize an automated design of drug and other chemical structures. The proposed approach searches an optimal structure of ligand that minimizes bond energy to the receptor protein...
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    2009 INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT 2009) 457 - + 2009年 [査読有り][通常論文]
     
    General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelization of Bayesian Optimization Algorithm (BOA) to solve complex combinatorial optimization problems over nVidia commodity graphics hardware using Compute Unified Device Architecture (CUDA). BOA is a well-known multivariate Estimation of Distribution Algorithm (EDA) that incorporates methods for learning Bayesian Network (BN). It then uses BN to sample new promising solutions. Our implementation is fully compatible with modern commodity GPUs and therefore we call it gBOA (BOA on GPU). In the results section, we show several numerical tests and performance measurements obtained by running gBOA over an nVidia Tesla C1060 GPU. We show that in the best case we can obtain a speedup of up to 13x.
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    2009 INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT 2009) 457 - + 2009年 [査読無し][通常論文]
     
    General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelization of Bayesian Optimization Algorithm (BOA) to solve complex combinatorial optimization problems over nVidia commodity graphics hardware using Compute Unified Device Architecture (CUDA). BOA is a well-known multivariate Estimation of Distribution Algorithm (EDA) that incorporates methods for learning Bayesian Network (BN). It then uses BN to sample new promising solutions. Our implementation is fully compatible with modern commodity GPUs and therefore we call it gBOA (BOA on GPU). In the results section, we show several numerical tests and performance measurements obtained by running gBOA over an nVidia Tesla C1060 GPU. We show that in the best case we can obtain a speedup of up to 13x.
  • An Automated Ligand Evolution System using Bayesian Optimization Algorithm
    WSEA Transactions on Information Science and Applications 6 5 788 - 797 2009年 [査読無し][通常論文]
  • De Novo Ligand Evolution using Bayesian Optimization Algorithms
    Proceedings of the 10th WSEAS International Conference on Evolutionary Computing 126 - 131 2009年 [査読無し][通常論文]
  • Munawar Asim, Wahib Mohamed, Munetomo Masaharu, Akama Kiyoshi
    Genetic Programming and Evolvable Machines 10 4 391 - 415 Springer 2009年 [査読無し][通常論文]
     
    General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design and software development. In this paper we describe the challenges and design choices involved in parallelizing a hybrid of Genetic Algorithm (GA) and Local Search (LS) to solve MAXimum SATisfiability (MAX-SAT) problem on a state-of-the-art nVidia Tesla GPU using nVidia Compute Unified Device Architecture (CUDA). MAX-SAT is a problem of practical importance and is often solved by employing metaheuristics based search methods like GAs and hybrid of GA with LS. Almost all the parallel GAs (pGAs) designed in the last two decades were designed for either clusters or MPPs. Unfortunately, very little research is done on the implementation of such algorithms over commodity graphics hardware. GAs in their simple form are not suitable for implementation over the Single Instruction Multiple Thread (SIMT) architecture of a GPU, and the same is the case with conventional LS algorithms. In this paper we explore different genetic operators that can be used for an efficient implementation of GAs over nVidia GPUs. We also design and introduce new techniques/operators for an efficient implementation of GAs and LS over such architectures. We use nVidia Tesla C1060 to perform several numerical tests and performance measurements and show that in the best case we obtain a speedup of 25×. We also discuss the effects of different optimization techniques on the overall execution time.
  • Munetomo Masaharu, Murao Naoya, Akama Kiyoshi
    Information Sciences 178 1 152 - 163 Elsevier Inc. 2008年01月02日 [査読無し][通常論文]
     
    In this paper, we improve Bayesian optimization algorithms by introducing proportionate and rank-based assignment functions. A Bayesian optimization algorithm builds a Bayesian network from a selected sub-population of promising solutions, and this probabilistic model is employed to generate the offspring of the next generation. Our method assigns each solution a relative significance based on its fitness, and this information is used in building the Bayesian network model. These assignment functions can improve the quality of the model without performing an explicit selection on the population. Numerical experiments demonstrate the effectiveness of this method compared to a conventional BOA.
  • M. Wahib, Asim Munawar, Masaharu Munetomo, Akama Kiyoshi
    2008 9TH IEEE/ACM INTERNATIONAL CONFERENCE ON GRID COMPUTING 316 - + 2008年 [査読無し][通常論文]
     
    MHGrid (Meta Heuristics Grid), a service oriented grid application offering global optimization solvers, allows developers to integrate their solvers and objective functions through an easy-to-use transparent mechanism. As a consequence of offering such a service, MHGrid hosts solvers and objective functions implementing diverse parallelization models leading later to different job grain size. Yet, the flexibility of the existing grid programming tools is limited if used individually. This paper proposes a model that uses a combination of grid parallel programming tools to enable the developers of MHGrid to specify their own parallelization model. Using this model the end user can choose the parallel model of the solver/objective function pair generating the grain size most appropriate to the problem in hand.
  • M. Wahib, Asim Munawar, Masaharu Munetomo, Akama Kiyoshi
    2008 9TH IEEE/ACM INTERNATIONAL CONFERENCE ON GRID COMPUTING 346 - + 2008年 [査読無し][通常論文]
     
    Since the introduction of grid computing various efforts were directed towards integrating and combining the grid with SOA technologies. That was mainly motivated by capitalizing on the widely desirable properties of SOA technologies. Nevertheless, the combination of SOA with grid computing in real practice is mainly tangible in the alignment of grid technologies with Web services. Therefore the effects were merely noticeable in the application layer and were more likely to define a SOA model for inner components' interactions. The deficient combination of grid with SOA needs to be deeply investigated to reach a comprehensive integration of grid with SOA that starts from the application layer till lower grid middleware layers. A major impact in this integration is offering application layer functionalities as services and thus having application specific QoS attributes originating from the application layer to be included in job scheduling. This paper presents integrating Grid computing with SOA into a generic Service Oriented Architecutered Grid (SOAG) model. A SOAG model for MHGrid -a service-oriented grid application for solving global optimization problems-is also briefly introduced.
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    HPCC 2008: 10TH IEEE INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS, PROCEEDINGS 131 - + 2008年 [査読無し][通常論文]
     
    This paper presents a method to solve large instances of Capacitated Vehicle Routing Problem (CVRP) using Cellular Genetic Algorithm (cGA) with Local Search (LS) over Cell Broadband Engine (Cell BE) architecture. We propose a unique parallelization model where computationally intensive Local Search (LS) runs on the available Synergistic Processing Elements (SPEs) in parallel, while the Power Processor Element (PPE) runs the cGA and acts as a controller for all the SPEs. We reproduce the results from earlier work in PPE only implementation of the algorithm, and we show a considerable reduction in execution time for parallel implementation over Cell BE. Moreover we extended it further to solve larger instances of CVRP (compared to the ones present in the CVRP literature), and got acceptable results in a reasonable amount of time.
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    HPCC 2008: 10TH IEEE INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING AND COMMUNICATIONS, PROCEEDINGS 897 - + 2008年 [査読無し][通常論文]
     
    This paper gives a survey about the impact of modern parallel/distributed computing paradigms over Parallel Genetic Algorithms (PGAs). Helping the GA community to feel more comfortable with the evolving parallel paradigms, and marking some areas of research for the High-Performance Computing (HPC) community is the major inspiration behind this survey. In the modern parallel computing paradigms we have considered only two major areas that have evolved very quickly during the past few years, namely, multicore computing and Grid computing. We discuss the challenges involved, and give potential solutions for these challenges. We also propose a hierarchical PGA suitable for Grid environment with multicore computational resources.
  • M. Wahib, Asim Munawar, Masaharu Munetomo, Akama Kiyoshi
    2008 IEEE INTERNATIONAL CONFERENCE ON SERVICES COMPUTING, PROCEEDINGS, VOL 2 563 - + 2008年 [査読無し][通常論文]
     
    MetaHeuristics Grid (MHGrid) is a service oriented Grid application that enables the user to solve almost any global optimization problem using metaheuristics techniques. Two problems potentially limit the generality of MHGrid over the problem type space; having a fixed set of solvers and lacking the solver-problem relation semantics. The set of strategies enforced to resolve these two problems are: offering the solvers as services, enabling the user to define his parallelization model, allowing the user to add his own service and maintaining service-based functionalities on both the middleware layer and application layer This paper explains the design, architecture and implementation of the SOA that MHGrid endorses that would allow the enforcing of the resolving strategies.
  • Empirical Investigations on Parallel Competent Genetic Algorithms
    Proceedings of the 2008 Genetic and Evolutionary Computation Conference 1073 - 1080 2008年 [査読無し][通常論文]
  • 棟朝 雅晴
    システム/制御/情報 52 10 362 - 367 システム制御情報学会 2008年 [査読無し][通常論文]
     
    「進化計算の新展開特集号」解説
  • Asim Munawar, Mohamed Wahib, Masaharu Munetomo, Kiyoshi Akama
    Studies in Computational Intelligence 157 159 - 187 2008年 [査読有り][通常論文]
     
    This chapter describes the latest trends in the field of parallel/ distributed computing and the effect of these trends over Genetic and Evolutionary Algorithms (GEAs) especially linkage based GEAs. We concentrate mainly on the Grid computing paradigm which is widely accepted as the most distributed form of computing due to the advent of Service Oriented Architecture (SOA) and other technologies, Grid has gained a lot of attention in the recent years. We also present a framework that can help users in implementation of metaheuristics based optimization algorithms (including GEAs) over a Grid computing environment. We call this framework MetaHeuristics Grid (MHGrid). Moreover, we give a theoretical analysis of the maximum speed-up achievable by using MHGrid. We also discuss our experience of working with Grids. © 2008 Springer-Verlag Berlin Heidelberg.
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    Studies in Computational Intelligence 157 441 - 459 2008年 [査読有り][通常論文]
     
    Efficient mixing of building blocks is important for genetic algorithms and linkage identification methods that identify interdependent variables tightly linked to form a building block have been proposed. However, they have not been applied to real-world problems enough. In this chapter, we apply a genetic algorithm incorporating a linkage identification method called D5 and a crossover method called CDC to a network design problem to verify its performance and examine the applicability of linkage identification genetic algorithms. © 2008 Springer-Verlag Berlin Heidelberg.
  • Miwako Tsuji, Masaharu Munetomo
    Studies in Computational Intelligence 137 251 - 279 2008年 [査読有り][通常論文]
     
    A series of advanced techniques in genetic and evolutionary computation have been proposed that analyze gene linkage to realize competent genetic algorithms. Although it is important to encode linked variables tightly for simple GAs, it is sometimes difficult because it requires enough knowledge of problems to be solved. In order to solve real-world problems effectively even if the knowledge is not available, we need to analyze gene linkage. We review algorithms which have been proposed that identify linkage by applying perturbations, by building a probabilistic model of promising strings, and a recombination of the both of the above. We also introduce a context-dependent crossover that can utilize overlapping linkage information in a sophisticated manner. By employing linkage identification techniques with context dependent crossover, we can solve practical real-world application problems that usually have complex problem structures without knowing them before optimization. © 2008 Springer-Verlag Berlin Heidelberg.
  • 辻 美和子, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌. 数理モデル化と応用 48 15 23 - 33 一般社団法人情報処理学会 2007年10月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズムによる効率的な探索のために,同一のビルディングブロック(building block, BB)を構成する遺伝子座の集合を検出する手法は多く提案されている(Heckendornら).しかしながら,これらの手法から得られたリンケージ情報を利用して効果的に交叉を行う方法については,十分な検討がなされてこなかった.特に重複するBBを持つ問題ではYuら(2005)の交叉手法のみが知られている.しかし,彼らの手法はBBの重複構造が複雑になったとき,頻繁にBBを破壊し,かつ十分な交叉パターンが得られないために,効率的に機能しない.本論文では,Yuらの手法を拡張し,BB破壊をできるだけ抑えながら,新たな異なる探索点を与える交叉手法を提案する.提案される手法は,コンテクスト依存交叉(Context Dependent Crossover, CDC)と呼ばれ,与えられた親個体組の値を調査したうえで,交換する遺伝子座を決定する.CDCは,リンケージ同定手法と併用されることで,重複するBBを持つ問題を探索する強力なアルゴリズムを提供する.また,提案手法の性能を確認するために,重複の複雑さが制御可能なテスト関数を設計する.
  • M. Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    EIGHTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PROCEEDINGS 167 - + 2007年 [査読無し][通常論文]
  • 複雑なビルディングブロック重複を持つ問題に対する交叉手法の提案
    情報処理学会論文誌「数理モデル化と応用」 48 SIG15 23 - 33 2007年 [査読無し][通常論文]
  • Asim Munawar, Masaharu Munetomo, Kiyoshi Akama
    2007 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-10, PROCEEDINGS 1191 - + 2007年 [査読無し][通常論文]
     
    This paper is a step towards a general purpose optimization problem-solving framework that can solve a large number of global optimization problems on its own with a minimal input from the user. It relies on competent GAs (Genetic Algorithms) as the solver and depends on Grid computing for the required computational resources. In this paper we will discuss the architecture of the framework in detail. In the results section we will discuss the speedups obtained by using parallel GAs over a Grid computing environment and the effects of Grid overheads on the speedup. Even though there are various advantages of using Grids but in the results section we will focus on the reduction in total execution time due to parallelism.
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    2007 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-10, PROCEEDINGS 349 - 356 2007年 [査読無し][通常論文]
     
    Efficient mixing of building blocks is important for genetic algorithms and linkage identification that identify variables tightly linked to form a building block have been proposed. In this paper, we apply D-5-GA with CDC - a genetic algorithm incorporating a linkage identification method called D-5 and a crossover method called CDC - to a network design problem to verify its performance and examine the applicability of the linkage identification genetic algorithms.
  • Standardization of Interfaces for Meta-Heuristics based Problem Solving Framework over Grid Environment
    Proceedings of the HPC Asia 2007 129 - 136 2007年 [査読無し][通常論文]
  • On Hybridization of Bayesian Optimization and Tabu Search
    Proceedings of the Seventh Metaheuristics International Conference (CD-ROM) 52  2007年 [査読無し][通常論文]
  • Masaharu Munetomo, Yuta Satake, Kiyoshi Akama
    COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 465 - + 2007年 [査読無し][通常論文]
     
    This paper proposes an efficient optimization algorithm based on tabu search and estimation of distribution algorithms. The proposed algorithm estimates characteristics of distribution of solutions after performing tabu searches based on a marginal product model to acquire linkage information. Once correct linkage information is obtained, we can perform crossovers effectively without disrupting building blocks using the information. The proposed algorithm is expected to adapt to both global and local characteristics of solution space. Through empirical studies, we show the effectiveness of our approach.
  • Masaharu Munetomo, Asim Munawar, Kiyoshi Akama
    COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 473 - + 2007年 [査読無し][通常論文]
     
    This paper presents a problem-solving framework based on robust evolutionary search in GRID computing environment. Our problem-solving environment called virtual innovative laboratory performs simulator programs in parallel and optimize their input parameters employing a competent evolutionary algorithm with gene analysis. The objective of our project is to replace a part of human designer's try-and-error processes by a parallel and robust evolutionary search on GRID computing systems.
  • Masaharu Munetomo, Yuta Satake, Kiyoshi Akama
    COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 465 - + 2007年 [査読無し][通常論文]
     
    This paper proposes an efficient optimization algorithm based on tabu search and estimation of distribution algorithms. The proposed algorithm estimates characteristics of distribution of solutions after performing tabu searches based on a marginal product model to acquire linkage information. Once correct linkage information is obtained, we can perform crossovers effectively without disrupting building blocks using the information. The proposed algorithm is expected to adapt to both global and local characteristics of solution space. Through empirical studies, we show the effectiveness of our approach.
  • Masaharu Munetomo, Asim Munawar, Kiyoshi Akama
    COMPUTER AIDED SYSTEMS THEORY- EUROCAST 2007 4739 473 - + 2007年 [査読無し][通常論文]
     
    This paper presents a problem-solving framework based on robust evolutionary search in GRID computing environment. Our problem-solving environment called virtual innovative laboratory performs simulator programs in parallel and optimize their input parameters employing a competent evolutionary algorithm with gene analysis. The objective of our project is to replace a part of human designer's try-and-error processes by a parallel and robust evolutionary search on GRID computing systems.
  • On Hybridization of Bayesian Optimization and Tabu Search
    Proceedings of the Seventh Metaheuristics International Conference (CD-ROM) 52  2007年 [査読無し][通常論文]
  • Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama
    Studies in Computational Intelligence 51 417 - 434 2007年 [査読有り][通常論文]
     
    Fitness function of financial optimization problem is often evaluated by Monte-Carlo method which is based on stochastic sampling. In this chapter we deal with the trade-off between the accuracy of the fitness estimation and its computational overheads, and introduce a method to decide the number of samples that maximizes the efficiency of genetic algorithms for financial problems. We define an index called selection efficiency which shows how close the population approaches to takeover in a fixed amount of time. When selection efficiency is maximized, the population converges to good solution rapidly, and optimization progresses most efficiently. Selection efficiency is generally difficult to calculate analytically. Thus bootstrapping approach is employed to calculate selection efficiency. The method estimates selection efficiency from the empirical distribution. The method is applied to the optimization of the procurement plan problem, and it optimizes Value at Risk efficiently. © Springer-Verlag Berlin Heidelberg 2007.
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    Evolutionary Computation 14 4 383 - 409 2006年12月 [査読無し][通常論文]
     
    Genetic Algorithms perform crossovers effectively when linkage sets -sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D5), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs. © 2006 by the Massachusetts Institute of Technology.
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    Evolutionary Computation 14 4 383 - 409 2006年12月 [査読有り][通常論文]
     
    Genetic Algorithms perform crossovers effectively when linkage sets -sets of variables tightly linked to form building blocks - are identified. Several methods have been proposed to detect the linkage sets. Perturbation methods (PMs) investigate fitness differences by perturbations of gene values and Estimation of distribution algorithms (EDAs) estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of variables by estimating the distribution of strings clustered according to fitness differences. The proposed algorithm, called the Dependency Detection for Distribution Derived from fitness Differences (D5), can detect dependencies of a class of functions that are difficult for EDAs, and requires less computational cost than PMs. © 2006 by the Massachusetts Institute of Technology.
  • 手塚 大, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌数理モデル化と応用(TOM) 47 14 43 - 53 一般社団法人情報処理学会 2006年10月15日 [査読無し][通常論文]
     
    最適化問題が,独立に最適化可能な複数の部分問題で表される場合,部分問題ごとに扱うことによって解の探索を効率化できる.遺伝的アルゴリズム(GA)では,この部分問題を構成する遺伝子座の集合をリンケージグループといい,リンケージグループを識別する手法をリンケージ同定という.本論文では,実数値GAのリンケージを明確に定義する.この定義に基づいてリンケージの識別を行う2つのリンケージ同定手法,LINC-RとLIDI-Rを提案する.LINC-Rは目的関数の加法分解性,LIDI-Rは差分の符号独立性に基づいてリンケージの有無を判定する.これらの手法は直接的にリンケージを識別するため,効率的にリンケージ同定ができる.In the case that a problem is decomposable to a number of sub-problems which can be optimized independently, the problem is solved effectively by optimizing sub-problems separately. In optimization problems by means of genetic algorithms, a set of loci of which each sub-problem consists is called linkage group. Linkage identification is the method which recognizes linkage groups. In this paper, we define the linkage of Real-Coded GAs clearly. Then we propose two new linkage identification methods, LINC-R and LIDI-R, directly based on the definition. LINC-R is based on additive decomposability and LIDI-R is based on independency of the signature of difference of an objective function. These methods effectively identify linkages.
  • 手塚 大, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌. 数理モデル化と応用 47 14 43 - 53 一般社団法人情報処理学会 2006年10月15日 [査読無し][通常論文]
     
    最適化問題が,独立に最適化可能な複数の部分問題で表される場合,部分問題ごとに扱うことによって解の探索を効率化できる.遺伝的アルゴリズム(GA)では,この部分問題を構成する遺伝子座の集合をリンケージグループといい,リンケージグループを識別する手法をリンケージ同定という.本論文では,実数値GAのリンケージを明確に定義する.この定義に基づいてリンケージの識別を行う2つのリンケージ同定手法,LINC-RとLIDI-Rを提案する.LINC-Rは目的関数の加法分解性,LIDI-Rは差分の符号独立性に基づいてリンケージの有無を判定する.これらの手法は直接的にリンケージを識別するため,効率的にリンケージ同定ができる.
  • 手塚 大, 樋地 正浩, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌 47 3 701 - 710 一般社団法人情報処理学会 2006年03月15日 [査読無し][通常論文]
     
    近年,パーソナルコンピュータや携帯電話など多くの製品でライフサイクルの短期化が進んでいる.ライフサイクルが短くなると,需要と供給に差がある場合に,販売機会損失や在庫破棄損失などのリスクが高まる.商品の製造や仕入れの数量と期日を決定する供給計画は需要予測に基づいて行われる.需要予測は過去の販売履歴などをもとに統計的に予測されるが,ここでもライフサイクルの短期化によって統計処理に必要なデータが少なくなり,予測精度の低下を引き起こす原因になっている.これまでは計画責任者の経験に基づいて供給量と期日が決められてきた.しかし,このような状況下では,次第に供給の意思決定が企業収益に与える影響が大きくなってきており,定量的評価に基づく意思決定が不可欠となっている.本論文では,需要と供給からどのように利益がもたらされるかをモデル化し,粗利益,機会損失,破棄在庫量などの指標をモンテカルロ法により分析し定量的に評価するシステムを提案する.このシステムを2 つの事例に適用し,その有効性を示す.In recent years, the life-cycle of high-tech products such as personal computers and cellular phones is getting shortened. Shorter life-cycle makes the risk of opportunity loss and dead-stock disposal loss higher. Supply plan designates the quantity and the delivery date of products to supply. The plan is created based on forecasted demand in order to cover the demand. Statistical method is used to forecast, however, shorter life-cycle also makes it difficult to obtain enough amounts of historical record to conduct statistical analysis. Consequently, the forecast accuracy declines. Since the decision made on the supply plan has a greater impact on the profitability these days, the decision based on quantitative evaluation is essential to manufacturers and resellers. In this paper, the model which explains how the profit is produced from the demand and supply is constructed. Taking advantage of the model, gross profit, opportunity loss, and dead-stock disposal loss are analyzed with Monte-Carlo method and evaluated quantitatively. The application of the proposed system on two cases shows the effectiveness of the system.
  • 手塚 大, 樋地 正浩, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌 47 3 701 - 710 一般社団法人情報処理学会 2006年03月15日 [査読無し][通常論文]
     
    近年,パーソナルコンピュータや携帯電話など多くの製品でライフサイクルの短期化が進んでいる.ライフサイクルが短くなると,需要と供給に差がある場合に,販売機会損失や在庫破棄損失などのリスクが高まる.商品の製造や仕入れの数量と期日を決定する供給計画は需要予測に基づいて行われる.需要予測は過去の販売履歴などをもとに統計的に予測されるが,ここでもライフサイクルの短期化によって統計処理に必要なデータが少なくなり,予測精度の低下を引き起こす原因になっている.これまでは計画責任者の経験に基づいて供給量と期日が決められてきた.しかし,このような状況下では,次第に供給の意思決定が企業収益に与える影響が大きくなってきており,定量的評価に基づく意思決定が不可欠となっている.本論文では,需要と供給からどのように利益がもたらされるかをモデル化し,粗利益,機会損失,破棄在庫量などの指標をモンテカルロ法により分析し定量的に評価するシステムを提案する.このシステムを2つの事例に適用し,その有効性を示す.
  • Realizing Virtual Innovative Laboratory with Robust Evolutionary Algorithms over the GRID computing system
    Proceedings of the 6th International Conference on Recent Advance in Soft Computing 42 - 47 2006年 [査読無し][通常論文]
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2 1337 - + 2006年 [査読無し][通常論文]
     
    We propose a crossover method to combine complexly overlapping building blocks (BBs). Although there have been several techniques to identify linkage sets of loci o form a BB [4, 6, 7, 10, 11], the way to to realize effective crossover from the linkage information from such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu et al. [13] is the first and only known research, however it cannot perform well for problems with complexly overlapping BBs due to insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings minutely and defines which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. The method is combined with a scalable linkage identification technique to construct an efficient algorithm for problems with overlapping BBs. We design test functions with controllable complexity of overlap and test the method with the functions.
  • Control the Number of Samples to Estimate Fitness from the Perspective of Takeover Time and Optimization of Financial Criteria
    Proceedings of the 2006 IEEE Congress on Evolutionary Computation 388 - 394 2006年 [査読無し][通常論文]
  • Masaharu Munetomo, Yuta Satake, Kiyoshi Akama
    2006 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-6, PROCEEDINGS 2362 - + 2006年 [査読無し][通常論文]
     
    Probabilistic model-building genetic algorithms such as extended compact genetic algorithm (ECGA) are proposed to solve difficult problems for classical genetic algorithms. Probabilistic model-building process based on marginal product model needs extensive computational overheads in ECGA. This paper discusses ECGA with linkage re-utilization and local search to reduce its model-building cost. Through simulation studies, we show the effectiveness of our approach that can reduce overall computational overheads.
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    2006 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-6, PROCEEDINGS 209 - + 2006年 [査読無し][通常論文]
     
    Estimation of distribution algorithms (EDAs) are population based evolutionary algorithms derived from genetic algorithms (GAs). EDAs build probabilistic models of promising solutions to guide further exploration of the search space. They have been considered to behave in similar way to GAs. In this paper, we show their different behaviors and difficulties in applications of EDAs by designing an EDA difficult function in which schemata that are not consistent with problem structure sometimes overwhelm those that are.
  • Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama, Masahiro Hiji
    2006 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-6 81 - 87 2006年 [査読有り][通常論文]
     
    In this paper we discuss the optimization problems with noisy fitness function. On financial optimization problems, Monte-Carlo method is commonly used to evaluate the optimization criteria such as value at risk. The evaluation model is often very complex which needs considerable computational overheads. In order to realize efficient optimization of financial problems, we propose a method to decide the number of samples used to estimate the optimization criteria. Selection efficiency proposed in this paper is a index that shows how close the population approaches to the convergence to a good solution. In general, it is difficult to calculate selection efficiency analytically. Thus we also employ bootstrap method to estimate selection efficiency. The resulting algorithm is applied to the optimization of the procurement plan optimization problem. The result shows that Value at Risk of the problem is optimized efficiently by the proposed method.
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama: "Population Sizing of Dependency Detection by Fitness Difference Classification", Foundations of Genetic Algorithms - FOGA2005, Lecture Notes in Computer Science 3469:282-299 (2005)*
    2005年 [査読無し][通常論文]
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama: "Linkage Identification for Real-Values Loci by Fitness Difference Classification", Proceedings of 2005 Congress on Evolutionary Computation, 2:1317-1324 (2005)*
    2005年 [査読無し][通常論文]
  • Masaharu Munetomo, Naoya Murao, Kiyoshi Akama: "Empirical Studies on Parallel Network Construction of Bayesian Optimization Algorithms", Proceedings of 2005 Congress on Evolutionary Computation, 2:1524-1531 (2005)*
    2005年 [査読無し][通常論文]
  • M Munetomo, N Murao, K Akama
    2005 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-3, PROCEEDINGS 1524 - 1531 2005年 [査読有り][通常論文]
     
    This paper discusses a parallel optimization algorithm based on evolutionary algorithms with probabilistic model-building in order to design a robust search algorithm that can be applicable to a wide-spectrum of application problems effectively and reliably. Probabilistic model building genetic algorithm, which is also called estimation of distribution algorithm, is a promising approach in evolutionary computation and its parallelization has been investigated. We propose an improvement of parallel network construction in distributed Bayesian optimization algorithms which estimate distribution of promising solutions as Bayesian networks. Through numerical experiments on an actual parallel architecture, we show the effectiveness of our approach compared to the conventional parallelization. Also we perform experiments on a real-world application problem: protein structure predictions.
  • M Tsuji, M Munetomo, K Akama
    2005 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-3, PROCEEDINGS 1317 - 1324 2005年 [査読有り][通常論文]
     
    In order to enhance efficiency of genetic algorithms, it is important to identify a linkage set, i.e. a set of loci tightly linked to construct a building block. In this paper, we propose a novel linkage identification method for real-valued strings called the real-valued Dependency Detection for Distribution Derived from df (rD(5)). It can detect linkage sets with quasi-linear fitness evaluations. The rD(5) is designed based on the D-5 which has been proposed for binary strings. It detects dependencies of loci by estimating the distribution of strings classified according to fitness differences. The rD(5) and the LINC-R which is one of linkage identification methods proposed elsewhere, provide approximate equivalent information about a function to be solved, however, the rD(5) performs smaller number of fitness evaluations than the LINC-R for larger functions. Although estimation of distribution algorithms (EDAs) also estimate distribution of strings, it is difficult for EDAs to solve a function composed of exponentially scaled sub-functions. The proposed method, by contrast, can be applied to the function in the similar way to as to a function composed of uniformly scaled sub-functions which is easy for EDAs. We perform experiments to compare the proposed method with the LINC-R and to examine the scaling effect stability of the rD(5). We also investigate two parameters, that define the amount of perturbation (mutation) and that define the quantization level.
  • M Tsuji, M Munetomo, K Akama
    FOUNDATIONS OF GENETIC ALGORITHMS 3469 282 - 299 2005年 [査読有り][通常論文]
     
    Recently, the linkage problem has attracted attention from researchers and users of genetic algorithms and many efforts have been undertaken to learn linkage. Especially, (1) perturbation methods (PMs) and (2) estimation of distribution algorithms (EDAs) are well known and frequently employed for linkage identification. In our previous work [TMA04], we have proposed a novel approach called Dependency Detection for Distribution Derived from df (D-5) which inherits characteristics from both EDAs and PMs. It detects dependencies of loci by estimating the distributions of strings classified according to fitness differences and can solve EDA difficult problems requiring a smaller number of fitness evaluations. In this paper, we estimate population size for the D5 and its computation cost. The computation cost slightly exceeds O(l), which is less than the PMs and some of EDAs.
  • 手塚 大, 樋地 正浩, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌 45 10 2287 - 2296 一般社団法人情報処理学会 2004年10月15日 [査読無し][通常論文]
     
    供給計画は需要予測に基づいて立案されるが,確実な予測は不可能であり,不確実性をともなう.したがって供給計画の立案では利益を最大化するとともに,予測と現実の差異が経営に及ぼす影響,すなわちリスクを最小化する必要がある.従来から用いられてきた安全在庫に基づく供給計画立案法は機会損失に主眼をおいたものであった.本論文で提案する供給計画手法は,供給計画の不確実性をモンテカルロシミュレーションにより数値化し,遺伝的アルゴリズムによって利益,リスク,機会損失,計画期間末在庫などのうち,注目した指標についてパレート最適な解を求める.数値実験により,提案する手法が従来手法よりも優れた供給計画を立案することを確認した.Supply is planned to meet the future forecast. However, uncertainty is involeved in the supply plan since it is difficult to forecast the future demand accurately. The impact to business caused by the gap between the forecast and actual demand is called risk. Thus, supply planning methods which can maximize profit and minimize risk simultaneously is desired. The conventional method based on safety stock or buffer stock has been widely used, whose main purpose is to prevent the occurrance of opportunity loss. In order to simulate the uncertainty and evaluate the profit and risk, we introduced Monte Carlo simulation. According to the fitness calculated by the simulation, a genetic algorithm optimizes the profit, risk, opportunity loss, and final inventory quantity of supply planning problems. The approach was tested on the supply planning data and has achieved a remarkable result.
  • 手塚 大, 樋地 正浩, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌 45 10 2287 - 2296 一般社団法人情報処理学会 2004年10月15日 [査読無し][通常論文]
     
    供給計画は需要予測に基づいて立案されるが,確実な予測は不可能であり,不確実性をともなう.したがって供給計画の立案では利益を最大化するとともに,予測と現実の差異が経営に及ぼす影響,すなわちリスクを最小化する必要がある.従来から用いられてきた安全在庫に基づく供給計画立案法は機会損失に主眼をおいたものであった.本論文で提案する供給計画手法は,供給計画の不確実性をモンテカルロシミユレーションにより数値化し,遺伝的アルゴリズムによって利益,リスク,機会損失,計画期間末在庫などのうち,注目した指標についてパレート最適な解を求める.数値実験により,提案する手法が従来手法よりも優れた供給計画を立案することを確認した.
  • 辻 美和子, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌数理モデル化と応用(TOM) 45 2 22 - 31 一般社団法人情報処理学会 2004年02月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズムにおいて,ビルディングブロック破壊を防ぎ効率的に探索を行うための手段としてリンケージ同定が提案されている.リンケージ同定遺伝的アルゴリズムではビルディングブロックを構成する遺伝子座をあらかじめ調べ,単純遺伝的アルゴリズムでは暗黙に実行される問題の分割と組合せの処理を陽に実行する.しかし,実際の問題は,特にその規模が大きいとき,ビルディングブロックどうしも相互依存関係を持つような階層型の構造をとると考えられる.現在のリンケージ同定遺伝的アルゴリズムでは,遺伝子座どうしの相互依存関係は考慮されるものの,ビルディングブロックどうしは独立であるとして処理される.本論文では,遺伝子の値の摂動による適応度の変化量の非単調性に基づく単層型のリンケージ同定手法であるLIEM2(Linkage Identification with Epistasis Measure considering Monotonicity)を拡張し,現実の問題に存在する階層構造のモデルの探索を可能にする.階層型リンケージ同定では,ビルディングブロックどうしの依存関係を再帰的に検出する.加えて,多様なビルディングブロック侯補を保持するために,ニッチングを行う.To avoid building block destructions, linkage identification techniques are proposed, which tries to identify a set of loci tightly-linked explicitly before performing genetic optimizations. Real-world problems, especially large-scaled complex problems, sometimes take hierarchical structures in which building blocks have recursive interdependencies. Existing linkage identification algorithms only consider interactions between loci in a same building block and assume no interdependency between building blocks. In this paper, the LIEM2(Linkage Identification with Epistasis Measure considering Monotonicity) - a single layer linkage identification algorithm based on non-monotonicity conditions - is extended to identify hierarchical multilayered linkage groups in order to search more accurate structures of real-world problems. The hierarchical linkage identification identifies linkage groups hierarchically in a recursive manner employing niching which preserve various building block candidates.
  • 辻 美和子, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌. 数理モデル化と応用 45 2 22 - 31 一般社団法人情報処理学会 2004年02月15日 [査読無し][通常論文]
     
    伝的アルゴリズムにおいて,ビルディングブロック破壊を防ぎ効率的に探索を行うための手段としてリンケージ固定が提案されている.リンケージ固定遺伝的アルゴリズムではビルディングブロックを構成する遺伝子座をあらかじめ調べ,単純遺伝的アルゴリズムでは暗黙に実行される問題の分割と組合せの処理を陽に実行する.しかし,実際の問題は,特にその規模が大きいとき,ビルディングブロックどうしも相互依存関係を持つような階層型の構造をとると考えられる.現在のリンケージ固定遺伝的アルゴリズムでは,遺伝子座どうしの相互依存関係は考慮されるものの,ビルディングブロックどうしは独立であるとして処理される.本論文では,遺伝子の値の摂動による適応度の変化量の非単調性に基づく単層型のリンケージ固定手法であるLIEM2 (Linkage Identification with Epistasis Measure considering Monotonicity)を拡張し,現実の問題に存在する階層構造のモデルの探索を可能にする.階層型リンケージ固定では,ビルディングブロックどうしの依存関係を再帰的に検出する.加えて,多様なビルディングブロック候補を保持するために,ニッチングを行う.
  • Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama: Selection Efficiency and Sampling Error on Genetic Algorithms Optimization under Uncertainty, Proceedings of 2004 Simulated Evolution and Learning (SEAL2004), (CD-ROM) (2004)*
    2004年 [査読無し][通常論文]
  • Masaharu Munetomo, Naoya Murao, Kiyoshi Akama: "Empirical Investigations on Parallelized Linkage Identification", Parallel Problem Solving from Nature - PPSN VIII, Lecture Notes in Computer Science, 3242:322-331 (2004)*
    2004年 [査読無し][通常論文]
  • Naoya Murao, Masaharu Munetomo, Kiyoshi Akama: "Performance Comparison between Parallel GA Based on Linkage Identification and Parallel Bayesian Optimization Algorithm", Proceedings of the International Conference on Cybernetics and Information Technol・・・
    2004年 [査読無し][通常論文]
     
    Naoya Murao, Masaharu Munetomo, Kiyoshi Akama: "Performance Comparison between Parallel GA Based on Linkage Identification and Parallel Bayesian Optimization Algorithm", Proceedings of the International Conference on Cybernetics and Information Technologies, Systems and Applications (CITSA2004), 3:136-141 (2004)*
  • Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama: "Linkage Identification by Nonlinearity Check for Real-coded Genetic Algorithms", Genetic and Evolutionary Computation - GECCO2004 Part 2, Lecture Notes in Computer Science, 3103:222-233 (2004)*
    2004年 [査読無し][通常論文]
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama: "Modeling Dependencies of Loci with String Classification According to Fitness Differences", Genetic and Evolutionary Computation - GECCO2004 Part 2, Lecture Notes in Computer Science, 3103:246-257 (2004)*
    2004年 [査読無し][通常論文]
  • Hidehiro Kobayashi, Masaharu Munetomo, Kiyoshi Akama, Yoshiharu Sato
    Systems and Computers in Japan 35 3 37 - 45 2004年 [査読無し][通常論文]
     
    When stream communications which requires a certain bandwidth during a certain time is to be realized on an existing network, a bandwidth allocation algorithm that efficiently allocates network resources is crucial to satisfying user service requirements. In the optimization of allocation in a small-scale network, the most efficient approach is to have one node manage network information and perform allocation in a concentrated scheme. However, in bandwidth allocation the computation time required for optimization increases in proportion to the network scale, and distribution of the algorithm becomes necessary in the implementation. Another advantage of the distributed scheme is that allocations can be continued even if a fault arises in the network, which improves the fault tolerance of the algorithm. This paper investigates distribution of the bandwidth allocation algorithm by using a genetic algorithm. An improved algorithm is proposed which can cope with the fault when it occurs in the network by the reallocation of all communications. The proposed algorithm includes both local optimization to optimize the allocation at each node to reduce the computation time, and global optimization to optimize the whole network by the tournament method while performing local optimization in each node. Simulation experiments comparing the performance of the concentrated algorithm and the proposed algorithm are described. © 2004 Wiley Periodicals, Inc.
  • Masaharu Munetomo: "Estimation of Distribution Algorithms without Explicit Selections", Proceedings of The 8th World Multi-Conference on Systemics, Cybernetics and Informatics (SCI2004), 5:80-85 (2004)
    2004年 [査読無し][通常論文]
  • M Munetomo
    8TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL V, PROCEEDINGS 80 - 85 2004年 [査読有り][通常論文]
     
    This paper proposes estimation of distribution algorithms without explicit selections by introducing assignment functions in their probabilistic model building process. Estimation of distribution algorithms build a probabilistic model from a selected population of promising solutions, which is employed to generate offsprings of the next generation. Instead employing selections, our model employs assignment functions which give relative weight of strings in a given population. By the assignment functions, we can improve quality of model building without performing explicit selections. Through numerical experiments, we show the effectiveness of the proposed methods compared with conventional EDA methods.
  • M Tsuji, M Munetomo, K Akama
    GENETIC AND EVOLUTIONARY COMPUTATION GECCO 2004 , PT 2, PROCEEDINGS 3103 246 - 257 2004年 [査読有り][通常論文]
     
    Genetic Algorithms perform crossovers effectively when we can identify a set of loci tightly linked to form a building block. Several methods have been proposed to detect such linkage. Linkage identification methods investigate fitness differences by perturbations of gene values and EDAs estimate the distribution of promising strings. In this paper, we propose a novel approach combining both of them, which detects dependencies of loci by estimating the distribution of strings classified according to fitness differences. The proposed algorithm called the Dependency Detection for Distribution Derived from df (DDDDD or D-5) can detect dependencies of a problem which is difficult for EDAs requiring lower computation cost than linkage identifications.
  • M Munetomo, N Murao, K Akama
    PARALLEL PROBLEM SOLVING FROM NATURE - PPSN VIII 3242 322 - 331 2004年 [査読有り][通常論文]
     
    To solve GA-difficult problems in which we cannot ensure tight linkage in their encoding, advanced methods such as linkage identification techniques and estimation of distribution algorithms work effectively although they need some additional computational cost. The computation time can be reduced by employing parallel computers and several approaches have been proposed for their parallelized algorithms. This paper presents empirical results on parallelization of the linkage identification compared to that of an estimation of distribution algorithm.
  • N Murao, M Munetomo, K Akama
    ISAS/CITSA 2004: International Conference on Cybernetics and Information Technologies, Systems and Applications and 10th International Conference on Information Systems Analysis and Synthesis, Vol 3, Proceedings 136 - 141 2004年 [査読有り][通常論文]
     
    Genetic Algorithms (GAs) are considered robust optimization algorithms which can solve wide-spectrum of difficult problems such as combinatorial optimization problems. Still, there are some GA-difficult problems which cannot ensure tight linkage in encoding strings. In such problems, crossovers cannot perform effectively on loosely encoded strings due to building block disruptions. Recently, a series of advanced techniques in evolutionary computations have been proposed to solve such GA-difficult problems. As one of these techniques, linkage identification checks nonlinearity caused by bit-wise perturbations for pairs of loci. Another advanced technique is Estimation of Distribution Algorithms (EDAs) which estimates probabilistic distribution for populations, and the Bayesian Optimization Algorithm (BOA) is the most sophisticated method in the EDAs. These methods can solve GA-difficult problem, paying additional computational cost. Therefore, parallel versions of these techniques, parallel GA based on linkage identification and parallel BOA, are studied to reduce computation time. In this paper, we compare performance of the parallel GA based on linkage identification with that of parallel BOA in actual parallel computing environment From the results, we consider relations between performance of the algorithms and the characteristics of the problems to be solved. Finally, we make discussions on the problem domains which algorithm performs more efficiently.
  • M Tezuka, M Munetomo, K Akama
    GENETIC AND EVOLUTIONARY COMPUTATION GECCO 2004 , PT 2, PROCEEDINGS 3103 222 - 233 2004年 [査読有り][通常論文]
     
    Linkage identification is a technique to recognize decomposable or quasi-decomposable sub-problems. Accurate linkage identification improves GA's search capability. We introduce a new linkage identification method for Real-Coded GAs called LINC-R (Linkage Identification by Nonlinearity Check for Real-Coded GAs). It tests nonlinearity by random perturbations on each locus in a real value domain. For the problem on which the proportion of nonlinear region in the domain is smaller, more perturbations are required to ensure LINC-R to detect nonlinearity successfully. If the proportion is known, the population size which ensures a certain success rate of LINC-R can be calculated. Computational experiments on benchmark problems showed that the CA with LINGR outperforms conventional Real-Coded CAs and those with linkage identification by a correlation model.
  • Miwako Tsuji, Masaharu Munetomo, and Kiyoshi Akama: "Metropolitan Area Network Design Using GA Based on Hierarchical Linkage Identification", Genetic and Evolutionary Computation Part 2, Lecture Notes in Computer Science 2724:1616-1617 (2003)*
    2003年 [査読無し][通常論文]
  • Masaharu Munetomo, Naoya Murao, and Kiyoshi Akama: "A Parallel Genetic Algorithm Based on Linkage Identification", Genetic and Evolutionary Computation Part 1, Lecture Notes in Computer Science 2723:1222-1233 (2003)*
    2003年 [査読無し][通常論文]
  • Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2724 1614 - 1615 2003年 [査読有り][通常論文]
  • M Tsuji, M Munetomo, K Akama
    GENETIC AND EVOLUTIONARY COMPUTATION - GECCO 2003, PT II, PROCEEDINGS 2724 1616 - 1617 2003年 [査読有り][通常論文]
  • M Munetomo, N Murao, K Akama
    GENETIC AND EVOLUTIONARY COMPUTATION - GECCO 2003, PT I, PROCEEDINGS 2723 1222 - 1233 2003年 [査読有り][通常論文]
     
    Linkage identification algorithms identify linkage groups sets of loci tightly linked - before genetic optimizations for their recombination operators to work effectively and reliably. This paper proposes a parallel genetic algorithm (GA) based on the linkage identification algorithm and shows its effectiveness compared with other conventional parallel GAs such as master-slave and island models. This paper also discusses applicability of the parallel GAs that tries to answer "which method of the parallel GA should be employed to solve a problem?".
  • 棟朝 雅晴
    情報処理学会論文誌数理モデル化と応用(TOM) 43 10 6 - 13 一般社団法人情報処理学会 2002年11月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズム(Genetic Algorithm ,GA )はビルディングブロックを交叉により組み合わせることで効果的な探索を実現しているが,そのためにどの遺伝子座がビルディングブロックを構成しうるのかを調べるリンケージ同定が重要となる.リンケージ同定に関してはこれまでにも確率モデルに基づく方法や非線形性もしくは非単調性を基に判断する手法が提案されている.本論文では,遺伝子座間に存在する非線形性を検出することでリンケージ同定を行うLINC (Linkage Identi cation by Nonlinearity Check )を発展させ,それぞれの遺伝子座のペアに対してエピスタシス(非線形性)尺度を定義し,それに基づいてリンケージの同定を実現する手法を提案する.Genetic Algorithms realize e ective search by exchanging building blocks through genetic recombinations.To realize e ective genetic search,linkage identi cation becomes important which detects a set of loci tightly linked to form a building block.Several methods are already proposed to identify linkage such as linkage learning algorithms based on probabilistic models and linkage identi cation procedures based on nonlinearity or non-monotonicity detection. In this paper,we extend the Linkage Identi cation by Nonlinearity Check (LINC)which identies linkage based on nonlinearity detection by de ning an epistasis measure for each pair of loci to realize linkage identi cation with the epistasis measure.
  • 棟朝 雅晴
    情報処理学会論文誌. 数理モデル化と応用 43 10 6 - 13 一般社団法人情報処理学会 2002年11月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズム(Genetic Algorithm, GA)はビルディングブロックを交叉により組み合わせることで効果的な探索を実現しているが,そのためにどの遺伝子座がビルディングブロックを構成しうるのかを調べるリンケージ同定が重要となる.リンケージ同定に関してはこれまでにも確率モデルに基づく方法や非線形性もしくは非単調性を基に判断する手法が提案されている.本論文では,遺伝子座間に存在する非線形性を検出することでリンケージ同定を行うLINC(Linkage Identification by Nonlinearity Check)を発展させ,それぞれの遺伝子座のペアに対してエピスタシス(非線形性)尺度を定義し,それに基づいてリンケージの同定を実現する手法を提案する.
  • 辻 美和子, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌数理モデル化と応用(TOM) 43 7 80 - 91 一般社団法人情報処理学会 2002年09月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズムにおいてはビルディングブロックとなる遺伝子をストリング上で密に符号化することが重要である.しかし,ネットワーク設計問題では地形,通信要求,経路などさまざまな要素が互いに複雑に影響するため,適切な符号化を行うことは難しい.多くの既存研究はビルディングブロックの密な符号化について考慮しておらず,これを考慮していたとしても地理的な要素のみである.本論文では,遺伝子の値の摂動による適応度の変化を用いて問題に関する前知識なしにビルディングブロックの位置であるリンケージを同定する手法であるLIEM (Linkage Identi fication withEpistasis Measure )を導入し,ビルディングブロックを効率的に組み合わせ,遺伝的アルゴリズムによる効果的な解の探索を実行する.実験を行い,本論文による手法で設計されたネットワークといくつかの交叉手法,符号化手法による単純遺伝的アルゴリズムによって設計されたネットワークの敷設コストを比較しLIEM によるネットワーク設計の有用性を証明する.In geneticalgorithms, it is important to encode strings ensuring tight linkage for their building blocks. In network design problems, however, it is difficult to encode strings appropriately because network design is dependent not only on geographical constraints but also on other complex factors such as bias on traffic demands, routing policy, and so on. Although there 's many applications of genetic algorithms to network topology design, most of them haven 't paid attention to tight encoding of building blocks, or considered only geographical characteristics. In order to realize tight linkage among loci and realize effective genetic search, this paper introduces LIEM (Linkage Identi fication with Epistasis Measure) 竏誕 technique for identifying linkage sets, sets of loci tightly liked to form building blocks 竏稚o realize effective network design. Through empirical studies, we show the effectiveness of the network design with the LIEM compared to that with conventional genetic algorithms.
  • 辻 美和子, 棟朝 雅晴, 赤間 清
    情報処理学会論文誌. 数理モデル化と応用 43 7 80 - 91 一般社団法人情報処理学会 2002年09月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズムにおいてはビルディングブロックとなる遺伝子をストリング上で密に符号化することが重要である.しかし,ネットワーク設計問題では地形,通信要求,経路などさまざまな要素が互いに複雑に影響するため,適切な符号化を行うことは難しい.多くの既存研究はビルディングブロックの密な符号化について考慮しておらず,これを考慮していたとしても地理的な要素のみである。本論文では,遺伝子の値の摂動による適応度の変化を用いて問題に関する前知識なしにビルディングブロックの位置であるリンケージを同定する手法であるLIEM(Linkage Identification with Epistasis Measure)を導入し,ビルディングブロックを効率的に組み合わせ,遺伝的アルゴリズムによる効果的な解の探索を実行する.実験を行い,本論文による手法で設計されたネットワークといくつかの交叉手法,符号化手法による単純遺伝的アルゴリズムによって設計されたネットワークの敷設コストを比較しLIEMによるネットワーク設計の有用性を証明する。
  • 山口 直彦, 棟朝 雅晴, 赤間 清, 佐藤義治
    情報処理学会論文誌 43 7 2359 - 2367 一般社団法人情報処理学会 2002年07月15日 [査読無し][通常論文]
     
    インターネットに代表されるパケット通信ネットワークにおいて,ネットワーク資源を有効に使用するという観点から,遺伝的アルゴリズムを用いて複数の経路を生成し,それらの代替経路間で負荷を分散するアルゴリズムが提案されている.本論文では遺伝的アルゴリズムを用いた負荷分散ルーティングに対し,評価の高速化によりネットワークの状態観測を迅速に行うため,経路の評価にリンクの負荷を考慮したメトリックを導入し,さらにそれを用いてネットワークの負荷状態を反映した代替経路生成を行う遺伝的操作の実装を行う.ネットワークシミュレータを用いたシミュレーション実験により提案する手法の有効性を検証した.In packet switching networks such as the Internet,to utilize network resources effectively,routing algorithms with genetic algorithms have been proposed which generate alternative routes by genetic operators to balance loads among them and prevent congestions.This paper proposes adaptive genetic operators based on link load metric for the genetic routing algorithms in order to realize rapid evaluations of network load status and effective generations of alternative routes.Through simulation experiments performed on a network simulator,we show the effectiveness of the proposed method.
  • 山口 直彦, 棟朝 雅晴, 赤間 清, 佐藤 義治
    情報処理学会論文誌 43 7 2359 - 2367 一般社団法人情報処理学会 2002年07月15日 [査読無し][通常論文]
     
    インターネットに代表されるパケット通信ネットワークにおいて,ネットワーク資源を有効に使用するという観点から,遺伝的アルゴリズムを用いて複数の経路を生成し,それらの代替経路間で負荷を分散するアルゴリズムが提案されている,本論文では遺伝的アルゴリズムを用いた負荷分散ルーティングに対し,評価の高速化によりネットワークの状態観測を迅速に行うため,経路の評価にリンクの負荷を考慮したメトリックを導入し,さらにそれを用いてネットワークの負荷状態を反映した代替経路生成を行う遺伝的操作の実装を行う.ネットワークシミュレータを用いたシミュレーション実験により提案する手法の有効性を検証した.
  • 小林 英博, 棟朝 雅晴, 赤間 清, 佐藤 義治
    電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理 = The transactions of the Institute of Electronics, Information and Communication Engineers. D-I 85 5 445 - 452 一般社団法人電子情報通信学会 2002年05月01日 [査読無し][通常論文]
     
    既存のネットワーク上で一定時間,一定の帯域幅を必要とするストリーム通信を実現する場合,ユーザからのサービス要求を満たすにはネットワーク資源を効率的に配分する帯域幅割当てアルゴリズムが重要となる.小規模なネットワークにおける割当ての最適化は,あるノードがネットワーク情報を集中的に管理し一括した割当てを実行する方法が最も効率が良い.しかし,帯域幅割当てはネットワーク規模の増加に比例して最適化に必要とする計算時間が増加するため,実装を考慮した場合にはアルゴリズムの分散化が必要となる.また分散化することによりネットワーク障害が発生した場合でも割当てが可能となり,アルゴリズムの耐障害性が向上する.本論文では,既存の遺伝的アルゴリズムによる帯域幅割当てアルゴリズムの分散化を目的とし,同時にネットワーク障害が発生した場合に全通信の再割当てを行うことで障害への対応を実現した改良アルゴリズムを提案する.本アルゴリズムの特徴は,計算時間を軽減するために各ノードで割当ての最適化を実行する局所的最適化と,全ノードで局所的最適化を実行しながら勝ち抜き戦を行うことでネットワーク全体を最適化する大域的最適化とを組み合わせて構成していることである.更にシミュレーション実験を行うことで,集中型アルゴリズムと提案アルゴリズムの性能について検討する.
  • 「遺伝的アルゴリズムによる帯域幅割当てのための分散アルゴリズムの設計」
    『電子情報通信学会論文誌 D-I』 J85-D-I 5 445 - 452 2002年 [査読無し][通常論文]
  • Yuichi Yamamoto, Takahiko Ishikawa, Kiyoshi Akama, Masaharu Munetomo: "A Foundation for Algorithm Generation by Transforming Meta-descriptions", Proceedings of the 2002 International Conference on Fuzzy Systems and Knowledge Discovery, 12-716 (2002)*
    2002年 [査読無し][通常論文]
  • Masaharu Munetomo, Miwako Tsuji, Kiyoshi Akama: "Metropolitan Area Network Design Using GA Based on Linkage Identification with Epistasis Measures", Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning, 652-656 (2002)*
    2002年 [査読無し][通常論文]
  • Masaharu Munetomo: "Linkage Identification with Epistasis Measure Considering Monotonicity Conditions", Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning, 550-554 (2002)*
    2002年 [査読無し][通常論文]
  • Masaharu Munetomo: "Linkage Identification Based on Epistasis Measures to Realize Efficient Genetic Algorithms", Proceedings of the 2002 Congress on Evolutionary Computation, 1332-1337 (2002)*
    2002年 [査読無し][通常論文]
  • M Munetomo
    CEC'02: PROCEEDINGS OF THE 2002 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1 AND 2 1332 - 1337 2002年 [査読有り][通常論文]
     
    Genetic algorithms (GAs) process building blocks (BBs) mixed and tested through genetic recombination operators. To realize effective BB processing, linkage identification is essential which detects a set of loci tightly linked. This paper proposes a linkage identification with epistasis measures (LIEM) that detects linkage groups based on a pair-wise epistasis measure.
  • Masaharu Munetomo: The Genetic Adaptive Routing Algorithm, in Telecommunications Optimisation: Heuristic and Adaptive Methods, pp.151-166, John Weily & Sons*
    2001年 [査読無し][通常論文]
  • Hidehiro Kobayashi, Masaharu Munetomo, Kiyoshi Akama, and Yoshiharu Sato: A Distributed Algorithm for Bandwidth Allocation in Multimedia Networks, Proceedings of the 5th International Conference on Artificial Evolution, 251-262 (2001)*
    2001年 [査読無し][通常論文]
  • Masaharu Munetomo, Naohiko Yamaguchi, Kiyoshi Akama, and Yoshiharu Sato: Empirical Investigations oon the Genetic Adaptive Routing Algorithm in the Internet, Proceedings of the Congress on Evolutionary Computation 2001, 1236-1243 (2001)*
    2001年 [査読無し][通常論文]
  • Masaharu Munetomo: The Genetic Adaptive Routing Algorithm, in Telecommunications Optimisation: Heuristic and Adaptive Methods, pp.151-166, John Weily & Sons*
    2001年 [査読無し][通常論文]
  • M Munetomo, N Yamaguchi, K Akama, Y Sato
    PROCEEDINGS OF THE 2001 CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1 AND 2 1236 - 1243 2001年 [査読有り][通常論文]
     
    This paper discusses improvement of genetic operators and fitness evaluation policies of the genetic adaptive routing algorithm we have proposed elsewhere. First, we introduce a threshold policy in evaluating link load status that is commonly employed in dynamic load balancing algorithms. Second. we discuss policies to trigger link load status observations to evaluate fitness values. Third, we introduce adaptive path mutation and path crossover operators to enhance their ability to generate well-performed alternative routes. Through empirical studies, we investigate optimal way for the load status observations and validate the effectiveness of the adaptive genetic operators.
  • Masaharu Munetomo: The Genetic Adaptive Routing Algorithm, in Telecommunications Optimisation: Heuristic and Adaptive Methods, pp.151-166, John Weily & Sons (2000). *
    2000年 [査読無し][通常論文]
  • Masaharu Munetomo: Network Routing with the Use of Evolutionary Methods, in Computational Intelligence in Telecommunication Networks (分担 : Witold Pedrycz and Athanasios V. Vasilakos, editors), CRC Press (2000).
    2000年 [査読無し][通常論文]
  • Masaharu Munetomo, David E. Goldberg: Linkage Identification by Non-monotonicity Detection for Overlapping functions, Evolutionary Computation, vol.7, No.4, pp.377-398*
    1999年 [査読無し][通常論文]
  • Masaharu Munetomo, David E. Goldberg: A Genetic Algorithm Using Linkage Identification by Nonlinearity Check, Proceedings of the 1999 IEEE Conference on System, Man, and Cybernetics (1999)
    1999年 [査読無し][通常論文]
  • Masaharu Munetomo, David E. Goldberg: Identifying Linkage Groups by Nonlinearity/Non-monotonicity Detection, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), pp.433-440 (1999)
    1999年 [査読無し][通常論文]
  • Masaharu Munetomo, David E. Goldberg: Linkage Identification by Non-monotonicity Detection for Overlapping functions, Evolutionary Computation, vol.7, No.4, pp.377-398 (1999)
    1999年 [査読無し][通常論文]
  • Munetomo Masaharu, Goldberg David E
    Evolutionary Computation 7 4 377 - 398 MIT Press 1999年 [査読無し][通常論文]
     
    This paper presents the linkage identification by non-monotonicity detection (LIMD) procedure and its extension for overlapping functions by introducing the tightness detection (TD) procedure. The LIMD identifies linkage groups directly by performing order-2 simultaneous perturbations on a pair of loci to detect monotonicity/non-monotonicity of fitness changes. The LIMD can identify linkage groups with at most order of k when it is applied to O(2k) strings. The TD procedure calculates tightness of linkage between a pair of loci based on the linkage groups obtained by the LIMD. By removing l...
  • A Migration Scheme of the Genetic Adaptive Routing Algorithm
    Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato
    Proc. of IEEE Int. Conf. on Systems, Man and Cybernetics, 2774 - 2779 1998年07月 [査読有り][通常論文]
  • 棟朝 雅晴, 高井 昌彰, 佐藤義治
    情報処理学会論文誌 39 2 219 - 227 一般社団法人情報処理学会 1998年02月15日 [査読無し][通常論文]
     
    本論文では,遺伝的アルゴリズムにより代替経路のリストを生成するとともに,それらの間で通信パケットを確率的に分配することで負荷の分散をはかる適応型ルーティングアルゴリズムを提案する.RIPやSPFなど従来用いられてきたルーティングアルゴリズムではルーティングテーブルやリンク状態をネットワーク全体にブロードキャストするため,ネットワークが大規模化した場合に多くの通信コストを要し,ネットワーク全体の性能を低下させる.また,複数の良い代替経路がある場合でも1つの最短経路を集中して使用してしまう.本論文で提案するルーティングアルゴリズムは,実際に多数のパケットが使用している経路に関してのみ代替経路の生成およびその通信遅延時間の評価を行うため,ルーティングの情報交換に必要な通信コストを大きく削減することが可能となる.また,本アルゴリズムでは代替経路間でパケットを確率的に分配することで負荷の分散をはかる.離散事象シミュレーションに基づくネットワークシミュレータを構築し,比較実験を行った.その結果,従来手法に比べ少ない通信コストにより効果的なルーティングがなされていることが示された.This paper presents an adaptive routing algorthm which has load balancing mechanism among alternative paths by a genetic algorithm.Conventional routing algorithms such as RIP and SPF broadcast information on routing tables or link status in a network,which yields much communication overhead and degrades total performance when the network becomes large.Conventional routing algorithms only generate the shortest path to send a packet,even if some good alternative paths are available.Our routing algorithm generates alternative paths and observes communication latency only for paths frequently used.This mechanism greatly reduces communication cost for information exchanging of the routing.Moreover this algorithm realizes load balancing on the alternative paths by destributing packets among them.We perform simulation experiments using a discrete event simulator of network communication.The result of the experiments shows that our algorithm achieves effective routing with less communication overhead.
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治
    情報処理学会論文誌 39 2 219 - 227 一般社団法人情報処理学会 1998年02月15日 [査読無し][通常論文]
     
    本論文では, 遺伝的アルゴリズムにより代替経路のリストを生成するとともに, それらの間で通信パケットを確率的に分配することで負荷の分散をはかる適応型ルーティングアルゴリズムを提案する. RIPやSPFなど従来用いられてきたルーティングアルゴリズムではルーティングテーブルやリンク状態をネットワーク全体にブロードキャストするため, ネットワークが大規模化した場合に多くの通信コストを要し, ネットワーク全体の性能を低下させる. また, 複数の良い代替経路がある場合でも1つの最短経路を集中して使用してしまう. 本論文で提案するルーティングアルゴリズムは, 実際に多数のパケットが使用している経路に関してのみ代替経路の生成およびその通信遅延時間の評価を行うため, ルーティングの情報交換に必要な通信コストを大きく削減することが可能となる. また, 本アルゴリズムでは代替経路間でパケットを確率的に分配することで負荷の分散をはかる. 離散事象シミュレーションに基づくネットワークシミュレータを構築し, 比較実験を行った. その結果, 従来手法に比べ少ない通信コストにより効果的なルーティングがなされていることが示された.
  • 遺伝的アルゴリズムによる負荷分散機構を有する適応型ルーティング
    情報処理学会論文誌 Vol.38 No.2 219 - 227 1998年 [査読無し][通常論文]
  • Shuichi Moriguti, Masaharu Munetomo, Yoshiharu Sato: A Moving Average Method for Predicting Process Resource Usage Based on a State Transition Model, Proceedings of the 1998 Conference of the North American Fuzzy Information Processing Society, pp.82-85*
    1998年 [査読無し][通常論文]
  • Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato: A Migration Scheme for the Genetic Adaptive Routing Algorithm, Proceedings of the 1998 IEEE Conference on Systems, Man, and Cybernetics, pp.2774-2779*
    1998年 [査読無し][通常論文]
  • Shuichi Moriguti,Masaharu Munetomo,Yoshiharu Sato:A Moving Average Method for Predicting Process Resource Usage Based on a State Transition Model(North American Fuzzy Information Processing Society(NAFIPS'98),1998)
    1998年 [査読無し][通常論文]
  • Masaharu Munetomo,Yoshiaki Takai,Yoshiharu Sato:A Migration Scheme for the Genetic Adaptive Routing Algorithm (IEEE Conference on Systems,Man,and Cybernetics(SMC'98),1998)
    1998年 [査読無し][通常論文]
  • S Moriguchi, M Munetomo, Y Sato
    1998 CONFERENCE OF THE NORTH AMERICAN FUZZY INFORMATION PROCESSING SOCIETY - NAFIPS 82 - 85 1998年 [査読有り][通常論文]
     
    In this paper, we develop a prediction algorithm for process resource usage based on a state-transition model, The state transition model is built by using a k-means clustering algorithm. applied to a series of 2-dimensional observed parameters on process resource usage such as Load average and Free memory in computer. Our prediction algorithm. estimates the parameters from state transition probabilities of the model. To reduce prediction error, we introduce a moving average method in the prediction algorithm..
  • An Intelligent Network Routing Algorithm by a Genetic Algorithm
    Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato
    Proc. of the 4th Int. Conf. on Neural Information Processing 1 547 - 550 1997年11月 [査読有り][通常論文]
  • An Adaptive Network Routing Algorithm Employing Path Genetic Operators
    Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato
    Proc. of the 7th Int. Conf. on Genetic Algorithms 643 - 649 1997年07月 [査読有り][通常論文]
  • 冨川 裕樹, 棟朝 雅晴, 高井 昌彰
    電子情報通信学会論文誌. D-2, 情報・システム 2-情報処理 80 2 700 - 702 一般社団法人電子情報通信学会 1997年02月25日 [査読無し][通常論文]
     
    強化学習機構を有する遺伝的アルゴリズム (StGA) [1], 利得行列の内容が不可視であり, 可能な行動の数が多いゲームヘ適用する. StGAのもととなった確率学習オートマトンとの比較実験を通し, こうしたゲームに対するStGA適用の有効性を検証する.
  • 「利得行列が不可視である行列ゲームへのStGAの適用」
    『電子情報通信学会論文誌』 J80-D-II 2 700 - 702 1997年 [査読無し][通常論文]
  • Munetomo, M., Takai, Y. and Sato, Y. : "An Adaptive Network Routing Algorithm Employing Path Genetic Operators", Proceedings of the Seventh International Conference on Genetic Algorithms, 643-649 (1997)*
    1997年 [査読無し][通常論文]
  • Munetomo, M., Takai, Y. and Sato, Y. : "An Intelligent Network Routing Algorithm by a Genetic Algorithm", Proceedings of the 1997 International Conference on Neural Information Processing and Intelligent Information Systems, 547-550 (1997)*
    1997年 [査読無し][通常論文]
  • Munetomo, M., Takai, Y. and Sato, Y. : "StGA : An Application of a Genetic Algorithm to Stochastic Learning Automata", Systems and Computers in Japan, 27(10) : 68-78 (1997)*
    1997年 [査読無し][通常論文]
  • StGA : An Application of a Genetic Algorithm to Stochastic Learning Automata
    Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato
    Systems and Computers in Japan 27 10 68 - 78 1996年10月 [査読有り][通常論文]
  • Masaharu Munetomo, Yoshiaki Takai, and Yoshiharu Sato: "Genetic-Based Dynamic Load Balancing: Implementation and Evaluation", Parallel Problem Solving from Nature, Lecture Notes in Computer Science 1141, 920--929 (1996)*
    1996年 [査読無し][通常論文]
  • Masaharu Munetomo, Yoshiaki Takai, and Yoshiharu Sato: "StGA: An application of a Genetic Algorithm to Stochastic Learning Automata", Systems and Computers in Japan, Vol.27, No.10, 68-78. (1996)*
    1996年 [査読無し][通常論文]
  • 「確率学習における遺伝的アルゴリズムの適用」
    『電子情報通信学会論文誌』 J79-D-II 2 230 - 238 1996年 [査読無し][通常論文]
  • M Munetomo, Y Takai, Y Sato
    INFORMATION INTELLIGENCE AND SYSTEMS, VOLS 1-4 522 - 526 1996年 [査読有り][通常論文]
     
    A stochastic genetic algorithm(StGA) effectively searches an optimal action which maximizes the probability to have reward payoffs in stochastic environments by employing stochastic learning automata and genetic algorithms. This paper discusses tracking-ability of the StGA to environmental changes from theoretical and empirical points of view. In the theoretical investigation, we employ an inhomogeneous Markov chain to formulate state transition of the probability for a population of actions to have an optimal one. We perform theoretical investigations on change of the probability to create an optimal action and of the probability to lose all the optimal ones. Simulation experiments are performed to show the effectiveness of the StGA in changing environments whose penalty probability vectors gradually or suddenly change.
  • Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1141 920 - 929 1996年 [査読有り][通常論文]
     
    This paper presents an adaptive dynamic load balancing scheme employing a genetic algorithm which includes an evaluation mechanism of fitness values in stochastic environments. A sender-initiative task migration algorithm continues to send unnecessary requests for a task migration while the system load is heavy, which brings much overhead before the migration finishes. In a genetic-based dynamic load balancing scheme we propose, a small subset of computers to which the requests are sent off is adaptively determined by a learning procedure to reduce unnecessary requests. The learning procedure consists of stochastic learning automata and genetic operators applied to a population of strings each of which stands for a subset of computers to which task migration requests are sent off. We implement the proposed algorithm on an actual distributed system which consists of UNIX workstations. We show the effectiveness of our approach through empirical investigations on the distributed system.
  • 棟朝 雅晴, 高井 昌彰, 佐藤義治
    情報処理学会論文誌 36 4 868 - 878 一般社団法人情報処理学会 1995年04月15日 [査読無し][通常論文]
     
    分散システムを有効に利用するために、システム内の各計算機の負荷を一様化することが必要である。分散管理型の動的負荷均衡アノレゴリズムにおいては、それぞれの計算機で独立して負荷状態の観測およびタスク転送の決定を行う。本論文では、負荷の重い計算機からのタスク転送要求をマルチキャストで実現した分散管理型の動的負荷均衡アノレゴリズムを提案する。本手法の特徴は、タスク転送要求の送出先リストを符号化し、適応度評価に確率学習オートマトンを組み合わせた遺伝的アルゴリズムを用いることで転送要求の成功率を向上させることにある。シミュレーション実験により従来の手法との比較検討を行い、提案する手法がシステムの平均応答時間、タスク転送要求の成功率、および動的な負荷変化への適応性の点において優れていることを示した。
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治
    情報処理学会論文誌 36 4 868 - 878 一般社団法人情報処理学会 1995年04月15日 [査読無し][通常論文]
     
    分散システムを有効に利用するために,システム内の各計算機の負荷を一様化することが必要である.分散管理型の動的負荷均衡アルゴリズムにおいては,それぞれの計算機で独立して負荷状態の観測およびタスク転送の決定を行う.本論文では,負荷の重い計算機からのタスク転送要求をマルチキャストで実現した分散管理型の動的負荷均衡アルゴリズムを提案する.本手法の特徴は,タスク転送要求の送出先リストを符号化し,適応度評価に確率学習オートマトンを組み合わせた遺伝的アルゴリズムを用いることで転送要求の成功率を向上させることにある.シミュレーション実験により従来の手法との比較検討を行い,提案する手法がシステムの平均応答時間,タスク転送要求の成功率,および動的な負荷変化への適応性の点において優れていることを示した.
  • M MUNETOMO, Y TAKAI, Y SATO
    1995 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS, VOLS 1-5 4 3795 - 3799 1995年 [査読有り][通常論文]
  • 棟朝 雅晴, 高井 昌彰, 佐藤義治
    情報処理学会論文誌 35 9 1815 - 1827 一般社団法人情報処理学会 1994年09月15日 [査読無し][通常論文]
     
    本論文では集団分割に基づく並列遺伝的アルゴリズムにおいて、効率的な個体交換を行う交換アルゴリズムを提案する。集団分割による並列遺伝的アルゴリズムは、個体からなる集団をいくつかの部分集団に分割し、それぞれを並列計算機のプロセッサに割り当てて遺伝的アルゴリズムを実行することにより、中粒度の並列処理を実現するものである。この手法においては集団の一様化による探索効率の減沙を防ぐために部分集団間で通信ネットワークを介した個体交換を行う必要がある。マルチプロセッサシステムにおいてプロセッサ間通信量を減少させることがその性能を向上させる上で重要であるが、並列遺伝的アルゴリズムに関する従来の研究では、個体の交換がその必要性とは関わりなく一定世代ごとまたは一定確率で行われており、並列処理の効率が悪いと考えられる。本諭文で提案する個体交換アルゴリズムSigma-Exchangeは各部分集団内の適合度分布を観測し、適合度分布の標準偏差の値が一定割合減少した場合にのみ交換の手続きを起動することにより、少ないプロセッサ間通信でより精度の高い解を速く得ることを目的としている。提案する手法の有効性を示すために、非同期のメッセージ受渡しによる中粒度並列計算機であるマルチコンビュータネットワークを前提としたシミュレーション実験を行った。その緒果、代表的な組合せ最適化間題について、提案する手法が有効であることが示された。
  • Masaharu Munetomo, Yoshiaki Takai, Yoshiharu Sato
    Proc. of the First IEEE Conference on Evolutionary Computation 1 418 - 421 1994年06月 [査読有り][通常論文]
  • M MUNETOMO, Y TAKAI, Y SATO
    PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS 649 - 649 1993年 [査読有り][通常論文]

MISC

  • 塚本 遙日, 森本 大智, 平賀 元彰, 大倉 和博, 棟朝 雅晴 システム制御情報学会研究発表講演会講演論文集 65 851 -858 2021年05月26日
  • 棟朝 雅晴 情報処理学会論文誌数理モデル化と応用(TOM) 14 (1) i -i 2021年01月27日
  • 高橋寿徳, 棟朝雅晴 情報処理学会研究報告(Web) 2021 (MPS-132) 2021年
  • 西野直登, 桂大地, 棟朝雅晴, 棟朝雅晴 情報処理学会研究報告(Web) 2021 (MPS-132) 2021年
  • 棟朝 雅晴 情報処理学会論文誌数理モデル化と応用(TOM) 13 (2) i -i 2020年08月28日
  • 村田 忠彦, 市川 学, 後藤 裕介, 杉木 章義, 伊達 進, 塙 敏博, 原田 拓弥, 棟朝 雅晴, 李 皓 日本知能情報ファジィ学会 ファジィ システム シンポジウム 講演論文集 36 (0) 269 -272 2020年 

  • 森本 大智, 平賀 元彰, 大倉 和博, 松村 嘉之, 棟朝 雅晴 人工知能学会全国大会論文集 2020 (0) 2M5OS3b02 -2M5OS3b02 2020年 

    Swarm Robotics(SR)は多数の比較的単純なロボットを用いてロボット間,あるいはロボットと環境間の局所的な相互作用から所望の群れ行動の創発を目指す研究分野である. これまでSRでは車輪による移動ロボットを用いた研究が主流であった. 移動ロボットは速度などの制御が比較的簡単である反面,三次元空間における立体的かつ複雑な群れ行動を生成することが難しい. 本研究では多脚自律ロボットを用いた群れ行動の生成を行う. 多脚自律ロボットの集団では各ロボットの立体的な挙動により,アリが作る橋に見られるような複雑な群れ行動の生成が期待される. しかし,一般的に移動ロボットと比較して多脚自律ロボットを任意の方向へ移動させるためには,より複雑な制御則が必要となる. さらに群れ行動を生成するための制御則を移動のための制御則に組み込んでロボットの制御器を設計する必要がある, 本研究ではNeuroevolutionを用いたアプローチにより多脚自律ロボットの制御器を自動的に設計する. 計算機シミュレーションにより,多脚自律ロボットの群れ行動の生成が可能であることを示した.

  • 棟朝 雅晴 情報処理学会論文誌数理モデル化と応用(TOM) 12 (3) i -i 2019年12月23日
  • 杉木 章義, 棟朝 雅晴 オペレーションズ・リサーチ = Communications of the Operations Research Society of Japan : 経営の科学 64 (9) 507 -513 2019年09月
  • 藤田駿一, 棟朝雅晴 情報処理学会研究報告(Web) 2019 (CSEC-84) Vol.2019‐CSEC‐84,No.13,1‐6 (WEB ONLY) 2019年02月25日 [査読無し][通常論文]
  • 高橋 寿徳, 棟朝 雅晴 人工知能学会全国大会論文集 2019 (0) 4Rin140 -4Rin140 2019年 [査読無し][通常論文]
     

    本稿では,アクションゲーム学習に向けた神経進化におけるモジュラーネットワークによるアプローチを紹介する。 モジュラーネットワークの生成にあたってNEATを使用し,様々な条件のステージを学習させ,それらを組み合わせて より難易度の高いステージに対処できるネットワークを作成する。 ゲームのインスタンスにはPygameを用い,元のNEATと比較して提案手法の有効性を示す。

  • 藤田駿一, 棟朝雅晴 情報科学技術フォーラム講演論文集 17th 103‐106 2018年09月12日 [査読無し][通常論文]
  • 泉谷光祐, 棟朝雅晴 電気学会電子・情報・システム部門大会講演論文集(CD-ROM) 2018 ROMBUNNO.MC1‐5 2018年09月05日 [査読無し][通常論文]
  • 岡部太亮, 棟朝雅晴 情報処理学会研究報告(Web) 2018 (MPS-118) Vol.2018‐MPS‐118,No.29,1‐2(WEB ONLY) 2018年06月06日 [査読無し][通常論文]
  • 畑徹, 棟朝雅晴 情報処理学会研究報告(Web) 2018 (MPS-117) Vol.2018‐MPS‐117,No.23,1‐2 (WEB ONLY) 2018年02月22日 [査読無し][通常論文]
  • 岩井良成, 杉木章義, 棟朝雅晴 情報処理学会研究報告(Web) 2017 (OS-140) Vol.2017‐OS‐140,No.13,1‐6 (WEB ONLY) 2017年05月09日 [査読無し][通常論文]
  • 市居遼平, 棟朝雅晴 情報処理学会研究報告(Web) 2017 (ITS-68) Vol.2017‐ITS‐68,No.10,1‐7 (WEB ONLY) 2017年02月21日 [査読無し][通常論文]
  • 齋藤篤志, 山下雅喜, 三浦克宜, 棟朝雅晴 情報処理学会研究報告(Web) 2017 (MPS-112) Vol.2017‐MPS‐112,No.13,1‐6 (WEB ONLY) 2017年02月20日 [査読無し][通常論文]
  • 棟朝雅晴 電子情報通信学会技術研究報告 116 (124(ICM2016 8-23)) 85‐86 2016年06月30日 [査読無し][通常論文]
  • 齋藤篤志, 三浦克宜, 棟朝雅晴 電子情報通信学会技術研究報告 116 (120(NC2016 6-15)) 55‐56 2016年06月27日 [査読無し][通常論文]
  • 市居 遼平, 棟朝 雅晴, 杉木 章義 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 115 (504) 83 -88 2016年03月10日 [査読無し][通常論文]
  • 阿部友哉, 棟朝雅晴 情報処理学会研究報告(Web) 2016 (MPS-107) VOL.2016-MPS-107,NO.21 (WEB ONLY) 2016年03月01日 [査読無し][通常論文]
  • 岩坪潤, 棟朝雅晴 情報処理学会研究報告(Web) 2016 (MPS-107) VOL.2016-MPS-107,NO.22 (WEB ONLY) 2016年03月01日 [査読無し][通常論文]
  • 中野 翔, 渡邉 真也, 千葉 一永, 金崎 雅博, 棟朝 雅晴 計測自動制御学会システム・情報部門学術講演会講演論文集 (2015) 631 -635 2015年11月18日 
    多目的最適化によって得られた非劣解集合に対して設計者側の要求に基づいた傾向分析を実現する新たな分析支援システムの提案を行う.本システムは,従来までの相関ルールに基づく分析アプローチを改良したものであり,設計者側からの要求に即したルール抽出に特化することで,設計者の知りたい傾向をピンポイントで抽出することが可能となっている.
  • 三浦克宜, 齋藤篤志, 棟朝雅晴 情報処理学会研究報告(Web) 2015 (MPS-105) VOL.2015-MPS-105,NO.6 (WEB ONLY) 2015年09月22日 [査読無し][通常論文]
  • 棟朝 雅晴 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 115 (140) 43 -48 2015年07月16日 [査読無し][通常論文]
  • 三浦克宜, 齋藤篤志, 玉家武博, 棟朝雅晴 電子情報通信学会技術研究報告 115 (112(IBISML2015 1-26)) 215 -220 2015年06月16日 [査読無し][通常論文]
  • 玉家 武博, 齋藤 篤志, 三浦 克宜, 棟朝 雅晴 第77回全国大会講演論文集 2015 (1) 177 -178 2015年03月17日 
    クラウドサービスの多様化が進む中で、それぞれのユーザーが自身の要件に適したサービスを選択することが困難になりつつある。そこで本研究では、ユーザーの要件に適した、仮想マシン等からなる仮想システムを自動的に最適化し、構築するクラウドスケジューラの実現に向けた検討を行う。本研究で提案するシステムは,(1) インタークラウド環境におけるそれぞれのクラウドサービスに関する情報を提供するサービス,(2) ユーザーが構築する仮想システムの要求要件に基づいて最適化を行うサービス、(3) インタークラウド環境に仮想システムを自動的に構築するサービス、の3つのWebサービスによって構成される。
  • 水越 大貴, 棟朝 雅晴 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2014 (1) 1 -6 2014年12月02日 [査読無し][通常論文]
     
    インターネットにおけるセキュリティ上の脅威の一つとして DDoS 攻撃が深刻な問題になっている.DDoS 攻撃は一般に攻撃元の情報が改竄されているため,攻撃元の特定が非常に困難であり防ぐ事が難しい攻撃だといえる.また,攻撃パターンの学習によるパターンマッチングや,異常トラフィック検知などの手法が研究されているが,DDoS 攻撃において攻撃者はボットネット等を使用し、常に異なるトラフィックパターンの攻撃を仕掛けてくるため、過去のデータの解析から DDoS 攻撃を防ぐ事は非常に難しい.このような背景から,ネットワーク管理者は常に現在どのような攻撃が行われているかを監視、解析し,DDoS 攻撃に対処する必要性に迫られる.しかし,近年ネットワーク上を流れるトラフィック量は急激に増加しており,トラフィックの解析にはかなりの時間かかってしまう事が予測される.そこで本稿では,DDoS 攻撃に対し迅速に対処するシステムを作る事を目的とし,並列分散処理基盤である Hadoop 上での遺伝的アルゴリズムを使用したトラフィックパターンの解析手法を提案する。
  • 阿部友哉, 棟朝雅晴 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2014 (18) 1 -2 2014年09月18日 [査読無し][通常論文]
     
    プライベートクラウドやパブリッククラウドを連携させたインタークラウド環境が整備され,仮想的に計算資源を無限に利用できるような環境が実現されつつある.本研究ではそのようなインタークラウド環境を想定して大規模かつ複雑な設計問題を扱う最適化フレームワークを構築する.具体的にはシミュレーションを実行するスパコン,大規模なパラメータサーベイを行うための最適化エンジンや分散データベース,解を視覚的に評価するための可視化装置などの複数のシステムの連携によって,設計問題に関する設計パラメータを統一的に管理,共有し最適化を行う.このフレームワークを構築するにあたって連携システムの詳細設計を行った.
  • 瀬山貴仁, 坂東信太郎, 棟朝雅晴 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2014 (7) 1 -4 2014年07月14日 [査読無し][通常論文]
     
    本論文においては、ユーザーの負担を軽減するために、多人数が協調して解の評価を行うインタラクティブ進化計算の実装について議論する。実装にあたっては、クラウド PaaS(Platform as a Service) 基盤を前提としたスケーラブルなシステムを実現するためのシステム設計を行った。
  • 棟朝雅晴 情報処理学会研究報告. BIO, バイオ情報学 2014 (28) 1 -2 2014年06月18日 [査読無し][通常論文]
     
    プライベートクラウドおよびパブリッククラウドを全国規模で連携させたインタークラウド環境を想定し,大規模かつ複雑な設計問題の設計パラメータに関する情報を,設計者や最適化エンジンが共有,活用しつつ協調して設計を行うフレームワークについて検討する.具体的には,設計パラメータやその評価値等に関する情報を,スケーラブルな分散データベースシステム上に統合管理するとともに,シミュレーションプログラムや可視化システム等の連携を行うフレームワークを,インタークラウド環境における物理・仮想マシン群およびオブジェクトストレージを用いて実現するものである.
  • 棟朝 雅晴 電子情報通信学会技術研究報告. NC, ニューロコンピューティング 114 (104) 165 -166 2014年06月18日 
    プライベートクラウドおよびパブリッククラウドを全国規模で連携させたインタークラウド環境を想定し,大規模かつ複雑な設計問題の設計パラメータに関する情報を,設計者や最適化エンジンが共有,活用しつつ協調して設計を行うフレームワークについて検討する.具体的には,設計パラメータやその評価値等に関する情報を,スケーラブルな分散データベースシステム上に統合管理するとともに,シミュレーションプログラムや可視化システム等の連携を行うフレームワークを,インタークラウド環境における物理・仮想マシン群およびオブジェクトストレージを用いて実現するものである.
  • 棟朝雅晴 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2014 (28) 1 -2 2014年06月18日 [査読無し][通常論文]
     
    プライベートクラウドおよびパブリッククラウドを全国規模で連携させたインタークラウド環境を想定し,大規模かつ複雑な設計問題の設計パラメータに関する情報を,設計者や最適化エンジンが共有,活用しつつ協調して設計を行うフレームワークについて検討する.具体的には,設計パラメータやその評価値等に関する情報を,スケーラブルな分散データベースシステム上に統合管理するとともに,シミュレーションプログラムや可視化システム等の連携を行うフレームワークを,インタークラウド環境における物理・仮想マシン群およびオブジェクトストレージを用いて実現するものである.
  • 三浦信一, 滝澤真一朗, 松岡聡, 棟朝雅晴, 實本英之, 小林泰三 情報処理学会研究報告. [ハイパフォーマンスコンピューティング] 2014 (30) 1 -6 2014年02月24日 [査読無し][通常論文]
     
    平成 24 年度より運用が開始されている HPCI では,スーパコンピュータ 「京」 や基盤センター群が保有するスーパコンピュータ間の認証基盤統一,データ共有を実現している.しかしながら,既存のスーパコンピュータシステムはバッチキューでジョブ管理されていることや,計算ノードでの管理者権限がないため,OS や分散システムの研究開発を行う CS 系ユーザの利用環境条件を満たさない.また,インターネット上より各種データを取得し,それを用いた計算を行う場合や,得られた成果を外部に公開するには,スーパコンピュータの利用は不向きである.そこで我々は,利用者に対してシステムへの管理者権限を付与する広域分散システムのホスティング機能を提供する,先端ソフトウェア運用基盤を HPCI の枠組みの中で構築し,平成 26 年 4 月より本格運用を開始する.本稿では先端ソフトウェア運用基盤の設計,構築及び運用について紹介する.
  • 川勝 崇史, 棟朝 雅晴 情報処理学会研究報告. BIO, バイオ情報学 2013 (9) 1 -6 2013年12月04日 [査読無し][通常論文]
     
    災害対策や可用性の高いシステムを構築するために,分散クラウド環境における WEB システムの多目的資源最適割当モデルを提案する.モデル化にあたっては、ロードバランサーによるリクエストの負荷分散やスケールアウトが自動できるようなシステムを前提とし,ユーザーが求める SLA を満たしたサーバーのスケジューリングを行なう.最適化にあたっては,コスト・レスポンス・リクエスト処理量の三つの目的関数をパラメータとして多目的遺伝的アルゴリズムを用いた最適解の探索を行い,その妥当性・有効性について検証する.
  • 川勝 崇史, 棟朝 雅晴 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2013 (9) 1 -6 2013年12月04日 [査読無し][通常論文]
     
    災害対策や可用性の高いシステムを構築するために,分散クラウド環境における WEB システムの多目的資源最適割当モデルを提案する.モデル化にあたっては、ロードバランサーによるリクエストの負荷分散やスケールアウトが自動できるようなシステムを前提とし,ユーザーが求める SLA を満たしたサーバーのスケジューリングを行なう.最適化にあたっては,コスト・レスポンス・リクエスト処理量の三つの目的関数をパラメータとして多目的遺伝的アルゴリズムを用いた最適解の探索を行い,その妥当性・有効性について検証する.
  • Masataka Mizukoshi, Shintaro Bando, Martin Schlueter, Masaharu Munetomo 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2013 (11) 1 -4 2013年07月15日 [査読無し][通常論文]
     
    Since the data volume from various facilities keeps growing rapidly in recent years, "big data" processing frameworks such as Hadoop have been developed as a scalable architecture to process large amount of data in cloud computing environment. We focus on intrusion detection problems which require large amount of data to be processed in order to detect malicious attacks. In this paper we discuss a Hadoop implementation of a multiple classifier system to enhance performances of the learning process in intrusion detection.
  • 柏崎 礼生, 近堂 徹, 北口 善明, 楠田 友彦, 大沼 善朗, 中川 郁夫, 市川 臭平, 棟朝 雅晴, 高井 昌彰, 阿部 俊二, 横山 重俊, 下條 真司 電子情報通信学会技術研究報告 : 信学技報 112 (489) 105 -110 2013年03月14日 [査読無し][通常論文]
     
    大規模災害による危機意識の高まりから災害回復(Disaster Recover:DR)を実現するための技術として遠隔地データセンターでのバックアップや分散ストレージに注目が集まっている.現在我々はランダムアクセス性能の高さに特徴のある広域分散ストレージ環境を金沢大学,広島大学,Nilを中心として構築しており,本研究では本環境のI/O性能を評価し,この環境の有用性を示す.
  • 柏崎 礼生, 近堂 徹, 北口 善明, 楠田 友彦, 大沼 善朗, 中川 郁夫, 市川 昊平, 棟朝 雅晴, 高井 昌彰, 阿部 俊二, 横山 重俊, 下條 真司 電子情報通信学会技術研究報告 : 信学技報 112 (488) 105 -110 2013年03月14日 [査読無し][通常論文]
     
    大規模災害による危機意識の高まりから災害回復(Disaster Recover:DR)を実現するための技術として遠隔地データセンターでのバックアップや分散ストレージに注目が集まっている.現在我々はランダムアクセス性能の高さに特徴のある広域分散ストレージ環境を金沢大学,広島大学,NIIを中心として構築しており,本研究では本環境のI/O性能を評価し,この環境の有用性を示す.
  • 柏崎 礼生, 近堂 徹, 北口 善明, 楠田 友彦, 大沼 善朗, 中川 郁夫, 市川 昊平, 棟朝 雅晴, 高井 昌彰, 阿部 俊二, 横山 重俊, 下條 真司 研究報告インターネットと運用技術(IOT) 2013 (19) 1 -6 2013年03月07日 [査読無し][通常論文]
     
    大規模災害による危機意識の高まりから災害回復(Disaster Recover: DR)を実現するための技術として遠隔地データセンターでのバックアップや分散ストレージに注目が集まっている.現在我々はランダムアクセス性能の高さに特徴のある広域分散ストレージ環境を金沢大学,広島大学,NIIを中心として構築しており,本研究では本環境のI/O性能を評価し,この環境の有用性を示す.
  • 平島慶典, 三浦克宜, 棟朝雅晴 全国大会講演論文集 2013 (1) 563 -565 2013年03月06日 [査読無し][通常論文]
     
    本研究では、与えられた論文に対して、的確な研究分野を判定するためのツールを開発する。研究を発展させる上で、関連研究のサーベイは重要であり、そのためには論文の適切な研究分野を知ることは極めて大切である。適切な研究分野を発見する方法として過去の論文と照らし合わせる方法が考えられる。しかしそれには膨大な計算量が掛かるため、逐次処理ではコストがかかる。この問題を解決するために、並列計算を使用している。研究分野の位置づけを行うために、本論文ではMahoutによるクラスタリングを行っており、そのための計算は、Hadoopを利用した並列計算を使用している。
  • 田中一真, 棟朝雅晴, 赤間清 全国大会講演論文集 2013 (1) 469 -471 2013年03月06日 [査読無し][通常論文]
     
    複数天体の重力支援を利用した宇宙探査機の軌道最適化は,厳密解の発見が困難な,制約付き非線形多変数関数の最適化問題である.本研究では,欧州宇宙機関で公開されている軌道最適化問題を単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによって解く.
  • 合田憲人, 東田学, 坂根栄作, 天野浩文, 小林克志, 棟朝雅晴, 江川隆輔, 建部修見, 鴨志田良和, 滝澤真一朗, 永井亨, 岩下武史, 石川裕 情報処理学会論文誌トランザクション(CD-ROM) 2012 (2) 2013年
  • 竹中 貴治, 保田 俊行, 大倉 和博, 松村 嘉之, 棟朝 雅晴 精密工学会学術講演会講演論文集 2013 (0) 775 -776 2013年 
    スワームロボットシステムとは多数のロボットが局所的な環境・状況下での相互作用を通して群行動を創発するシステムである.本稿ではニューラルネットをCMA-ESにより最適化するCMA-NeuroESを制御器の設計に運用する.その際,進化の過程で膨大な計算コストが必要となるため,SMP Cluster型の大規模並列計算機で並列・高速化を図る.その上で,並列化を行う上で発生する同期待ち時間に着目し,実行時間短縮について考察する.
  • 梶田 将司, 棟朝 雅晴 電子情報通信学会 通信ソサイエティマガジン 7 (3) 166 -174 2013年 [査読無し][通常論文]
  • 合田 憲人, 東田 学, 坂根 栄作, 天野 浩文, 小林 克志, 棟朝 雅晴, 江川 隆輔, 建部修見, 鴨志田 良和, 滝澤 真一朗, 永井 亨, 岩下 武史, 石川 裕 情報処理学会論文誌コンピューティングシステム(ACS) 5 (5) 90 -102 2012年10月15日 
    本稿では,現在文部科学省により整備が進められている革新的ハイパフォーマンス・コンピューティング・インフラ (HPCI) のための認証基盤の設計について述べる.本認証基盤では,グリッド上の認証技術である Grid Security Infrastructure (GSI),および認証連携技術である Shibboleth を用いることにより, HPCI を構成する計算機や共用ストレージに対するシングルサインオンを実現する.本稿ではまた,本認証基盤の設計を検証するために構築した実験環境上での実証実験についても報告する.This paper presents design of the authentication system for the High Performance Computing Infrastructure (HPCI), which is currently deployed by the Ministry of Education, Culture, Sports, Science and Technology. The presented authentication system enables single sign-on to computers and shared storages on HPCI by utilizing the authentication mechanism on the Grid, "Grid Security Infrastructure (GSI)", and the identity federation mechanism, "Shibboleth". This paper also presents the experiments conducted on the testbed for the presented authentication system.
  • 川勝崇史, 棟朝雅晴 情報処理学会研究報告(CD−ROM) 2012 (3) ROMBUNNO.MPS-90,NO.13 2012年10月15日 [査読無し][通常論文]
  • 吉原郁夫, 本田詩織, 坂本亜衣, 山森一人, 棟朝雅晴 Mem Fac Eng Univ Miyazaki (41) 337-341 2012年07月30日 [査読無し][通常論文]
  • 吉原郁夫, 坂本亜衣, 本田詩織, 山森一人, 棟朝雅晴 Mem Fac Eng Univ Miyazaki (41) 331-335 2012年07月30日 [査読無し][通常論文]
  • 棟朝 雅晴, 堀田 多加志, 田中 誠司 日立評論 94 (7) 489 -491 2012年07月 [査読無し][通常論文]
  • 萩田 克美, 棟朝 雅晴, 上島 豊 計算工学講演会論文集 Proceedings of the Conference on Computational Engineering and Science 17 4p 2012年05月
  • 川江 修, 小原 伸哉, Balaji Rengaraja, 棟朝 雅晴 環境工学総合シンポジウム講演論文集 2012 (0) 393 -395 2012年 
    In this paper we consider the system to cover all energy by solar cells. System is composed of solar cells, PEFC, water electrolyzer, and heat pump. In this paper, we developed a analysis program by genetic algorithm. And, revealed the capacity of the equipment and two types of operational methods. A result of the analysis, equipment capacity needed in the first method of operating, solar cells is 250m2, PEFC is 8.1kW, water electrolyzer is 22.1kW, heat pump is 14.4kW, amount of hydrogen storage is 106.6kWh, amount of heat storage is 10.2kWh. In addition, equipment capacity needed in the second method of operating, solar cells is 300m2, PEFC is 4.7kW, water electrolyzer is 30.1kW, heat pump is 8.5kW, amount of hydrogen storage is 84.9kWh, amount of heat storage is 21.5kWh. To consider the cost of equipment as the next step.
  • 吉原 郁夫, 坂本 亜衣, 本田 詩織, 山森 一人, 棟朝 雅晴 宮崎大學工學部紀要 41 (41) 331 -335 2012年 [査読無し][通常論文]
     
    Multiple-precision calculation is necessary for precisely solving scientific engineering problems. Extremely long precision is employed to evaluate the mathematical constant, e.g. π, γ(Euler's constant), e(Nepier's constant) etc. To develope multiple-precision computing software, we try to calculate π with more than one million decimal digits. The proto-type code is verified by performing calculation with numerical examples and evaluated rapidness of calculation. Hother to π with 16,777,199 decimal digit is obtained.
  • 吉原 郁夫, 本田 詩織, 坂本 亜衣, 山森 一人, 棟朝 雅晴 宮崎大學工學部紀要 41 (41) 337 -341 2012年 [査読無し][通常論文]
     
    It is necessary to employ "multiple precision arithmetic" for computing long digit numbers, because numerical representation of computers is usually limited. This paper aims at making prototype software to compute more than one million digit numbers. A long digit number is divided into 2^n short digit numbers, each of which can be calculated by ordinal double precision arithmetic units. The key technique of "multiple precision arithmetic" is based on fast Fourier transform and convolution theorem. The prototype program is verified from the viewpoint of correctness of calculation up to 4 X 10^6 digits and speed up ratio vs theoretical value. The program is applied to calculation of a 10^7 or more digit π.
  • 堀伸哉, 棟朝雅晴, 赤間清 情報処理学会研究報告(CD−ROM) 2011 (3) ROMBUNNO.MPS-85,NO.16 2011年10月15日 [査読無し][通常論文]
  • 堀 伸哉, 棟朝 雅晴, 赤間 清 研究報告数理モデル化と問題解決(MPS) 2011 (16) 1 -6 2011年09月08日 [査読無し][通常論文]
     
    BOA (Bayesian Optimization Algorithm) はベイジアンネットワークと条件付確率を用いて問題の構造を詳細に表現することで、広範囲の問題を解くことのできる最適化アルゴリズムである。BOA はその特性から広範囲の問題を解くことができるが、環境が動的に変化するような問題に対しては、ベイジアンネットワークが一方の環境に対して収束し、結果として動的環境に対応できないという問題点がある。本論文は BOA に混合ベイジアンネットワークの概念を導入した BOA with Mixture Distribution (BOA-MD) に新しい追加要素を導入することでそのような問題の解決を目指す。そして、その効果を考察することによって BOA の問題解決領域を広げることを目的とする。Bayesian Optimization Algorithm (BOA) can solve wide-spectrum of optimization problems by modeling their probabilistic models with conditional probabilities based on Bayesian networks. BOA succeeds in solving a variety of difficult optimization problems, however, it has not been applied successfully to dynamic environment because it tend to converge at one specific network and cannot adapt to change of probabilistic distributions. In this paper, we propose a BOA that introduces mixture distributions and inheritance of probability distribution of previous generation to adapt to dynamic environment, and discuss effect of this introduction. Through these, this work motivates to broaden the optimization problem domain.
  • Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama 研究報告数理モデル化と問題解決(MPS) 2011 (6) 1 -6 2011年09月08日 [査読無し][通常論文]
     
    De Novo ligand design is an automatic fragment-based design of molecules within a protein binding site of a known structure. A Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, is introduced to join predocked fragments with a user-supplied list of fragments. A novel feature proposed is the simultaneous optimization of force field energy and a term enforcing 3D-overlap to known binding mode(s). The performance of algorithm is tested on Liver X receptors (LXRs) using a library of about 14,000 fragments and the binding mode of a known heterocyclic phenyl acetic acid to bias the design. We further introduce the use of GPU (Graphical Processing Unit) to overcome the excessive time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragment sets and target receptors for more complex instances. The Results show how the nVidia's Tesla C2050 GPU was utilized to enable the generation of complex agonists effectively. In fact, eight of the 1809 molecules designed for LXRs are found in the ZINC database of commercially available compounds.De Novo ligand design is an automatic fragment-based design of molecules within a protein binding site of a known structure. A Bayesian Optimization Algorithm (BOA), a meta-heuristic algorithm, is introduced to join predocked fragments with a user-supplied list of fragments. A novel feature proposed is the simultaneous optimization of force field energy and a term enforcing 3D-overlap to known binding mode(s). The performance of algorithm is tested on Liver X receptors (LXRs) using a library of about 14,000 fragments and the binding mode of a known heterocyclic phenyl acetic acid to bias the design. We further introduce the use of GPU (Graphical Processing Unit) to overcome the excessive time required in evaluating each possible fragment combination. We show how the GPU utilization enables experimenting larger fragment sets and target receptors for more complex instances. The Results show how the nVidia's Tesla C2050 GPU was utilized to enable the generation of complex agonists effectively. In fact, eight of the 1809 molecules designed for LXRs are found in the ZINC database of commercially available compounds.
  • 滝澤真一朗, 棟朝雅晴, 宇野篤也, 小林泰三, 實本英之, 松岡聡, 松岡聡, 石川裕 情報処理学会研究報告(CD−ROM) 2011 (2) ROMBUNNO.HPC-130,NO.68 2011年08月15日 [査読無し][通常論文]
  • 滝澤 真一朗, 棟朝 雅晴, 宇野 篤也, 小林 泰三, 實本 英之, 松岡 聡, 石川 裕 研究報告ハイパフォーマンスコンピューティング(HPC) 2011 (68) 1 -7 2011年07月20日 [査読無し][通常論文]
     
    平成24年秋の運用開始が予定されているHPCIではHPC研究者がスーパーコンピュータ「京」を有効活用することの支援を目的とし,京と基盤センター群が保有するスーパーコンピュータ間の認証基盤統一,データ共有の実現から開始する.しかしながら,スーパーコンピュータはバッチキューでジョブ管理されていることや,計算ノードでの管理者権限がないため,OSや分散システムの研究を行うHPC研究者向けの利用環境条件を満たさない.そこで我々は,利用者に対してシステムへの管理者権限を付与する広域分散システムのホスティング機能を提供する,先端ソフトウェア運用基盤を設計する.本稿では先端ソフトウェア運用基盤の設計,および,先行システムとして運用されているRENKEI-PoPによる事例を紹介する.The purpose of HPCI, which will be operated from autumn 2012, is to support HPC researchers to use K supercomputer, and its initial services are a federated authentication and global file sharing between K and supercomputers provided by computer centers in Japan. However, supercomputers are not suitable for HPC system researchers as their operations do not give users enough privileges. We design the advanced software deployment infrastructure that hosts distributed systems where researchers can have administrator privileges. We introduce the design of the system and a precedent system implemented on RENKEI-PoPs that use the same software.
  • WAHIB MOHAMED, MUNAWAR ASIM, MUNETOMO MASAHARU, Kiyoshi Akama 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 79 (9) I1 -I11 2010年07月12日 [査読無し][通常論文]
     
    Grid computing has gained a wide interest from the research community over the past one and a half decade. The immense effort has resulted in mature tools and technologies for grid computing. The utilization of experience and tools of grid computing in the next generation of distributed systems (e.g. cloud com-puting) is a logical step. However, many problems that come along with grid computing do limit such an effort. Among these problems is the sophistication of each production grid to a specific task type, size and dependency. In other words, grid computing in practice up to the moment can be described as task monolithic in terms of task scope. The approach to tackle this problem in this paper can be viewed as virtualizing the tasks to the middleware in analogy to how resources are virtualized, automatically provisioned and abstracted in current distributed systems trends. The task virtualization in this case refers to the ability of the system to host variant tasks through a generic transparent interface. This paper proposes a light-weight framework using various combined open-source grid tools to establish a grid-based system capable of executing tasks of different types, sizes and dependencies. From the middleware's perspective, designing and implementing such a model is challenged by 1) The need of a unified model for defining and representing the tasks, and 2) A tasks dispatching and execution manager. Experiments for using the framework in an optimization problem solving environment is illustrated. Performance results are presented showing the functional efficiency of the framework.Grid computing has gained a wide interest from the research community over the past one and a half decade. The immense effort has resulted in mature tools and technologies for grid computing. The utilization of experience and tools of grid computing in the next generation of distributed systems (e.g. cloud com-puting) is a logical step. However, many problems that come along with grid computing do limit such an effort. Among these problems is the sophistication of each production grid to a specific task type, size and dependency. In other words, grid computing in practice up to the moment can be described as task monolithic in terms of task scope. The approach to tackle this problem in this paper can be viewed as virtualizing the tasks to the middleware in analogy to how resources are virtualized, automatically provisioned and abstracted in current distributed systems trends. The task virtualization in this case refers to the ability of the system to host variant tasks through a generic transparent interface. This paper proposes a light-weight framework using various combined open-source grid tools to establish a grid-based system capable of executing tasks of different types, sizes and dependencies. From the middleware's perspective, designing and implementing such a model is challenged by 1) The need of a unified model for defining and representing the tasks, and 2) A tasks dispatching and execution manager. Experiments for using the framework in an optimization problem solving environment is illustrated. Performance results are presented showing the functional efficiency of the framework.
  • 堀伸哉, 棟朝雅晴, 赤間清 情報処理学会研究報告(CD−ROM) 2009 (6) ROMBUNNO.MPS-77,23 2010年04月15日 [査読無し][通常論文]
  • 堀 伸哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告 2009 (6) 1 -7 2010年04月 [査読無し][通常論文]
     
    本論文は BOA の改良型アルゴリズム、EBOA (Effective BOA) を提案する。EBOA は BOA のベイジアンネットワーク構築フェイズにおいて、探索する遺伝子ノード数をエントロピーの値によってクラスタリングし、それぞれのクラスターでベイジアンネットワークを構築することで遺伝子の探索時間を減少させる。また、これと同時にエントロピーの値による探索遺伝子数の絞込みも導入する。これら二つの手法を取り入れた EBOA は BOA において問題となる多大な実行時間を短縮することで複雑で巨大な問題の最適化を行うことが可能となる。This paper proposes an Effective Bayesian Optimization Algorithm (EBOA) which improves network construction process of BOA. EBOA performs clustering of locus nodes based on their entropy measures and at the same time, removes loci that are not necessary to be modeled based on their entropy. After the clustering, it constructs a Bayesian Network in each cluster to reduce the running time for searching networks for BOA to solve large and complex optimization problems.
  • 堀 伸哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2010 (23) 1 -7 2010年02月25日 [査読無し][通常論文]
     
    本論文は BOA の改良型アルゴリズム、EBOA (Effective BOA) を提案する。EBOA は BOA のベイジアンネットワーク構築フェイズにおいて、探索する遺伝子ノード数をエントロピーの値によってクラスタリングし、それぞれのクラスターでベイジアンネットワークを構築することで遺伝子の探索時間を減少させる。また、これと同時にエントロピーの値による探索遺伝子数の絞込みも導入する。これら二つの手法を取り入れた EBOA は BOA において問題となる多大な実行時間を短縮することで複雑で巨大な問題の最適化を行うことが可能となる。
  • Munawar Asim, Wahib Mohamed, Munetomo Masaharu, AKAMA KIYOSHI 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 69 (41) 23 -26 2008年05月09日 [査読無し][通常論文]
     
    This paper presents a Service Oriented Architecture (SOA) compliant Problem Solving Environment (PSE) that allows the user to implement any metaheuristics based algorithm over a Grid. We call this framework a Grid based Unified Framework for Optimization (GridUFO). GridUFO provides a unified approach for sharing and using metaheuristics algorithms (solvers) and objective functions over a Grid in an easiest possible "plug & play" manner. In this way the user can take all the advantages of the Grid without taking into consideration any of the complexities posed by the Grid environment. The framework is accessible to the user through a Web service or through a fully integrated 2nd generation Web portal. GridUFO provides well-defined interfaces between the user-programmed objective functions and solvers. We also present MetaHeuristics Markup Language (MHML), an XML based language that acts as an interface between the user and the framework. In this paper we will discuss the design and implementation of GridUFO in detail. Moreover, we will talk about our experience of working with Grids, and we will also make some recommendations for future research.
  • 佐竹 佑太, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 68 (17) 109 -112 2008年03月04日 [査読無し][通常論文]
     
    Bayesian Optimization Algorithm(BOA)は集団の分布を表した確率モデルを構築し,構築したモデルを基に新たな個体を生成するアルゴリズムである.構築したモデルによって,互いに依存する複数の遺伝子を検出することができるため,BOAは広範囲の最適化問題を解くことができる.BOAの探索能力をさらに高めるためにBOAに局所探索法を組み込んだ手法が提案されている.しかしながら,新たな探索点を効果的に生成可能な散布探索法は局所探索法として用いられてこなかった.そこで,本論文では散布探索法をBOAに組み込んだ手法を提案し,その手法の有効性について検討する.
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. BIO, バイオ情報学 2007 (128) 171 -174 2007年12月20日 [査読無し][通常論文]
     
    事前知識によらずに自動的に問題構造を検出するコンペテント遺伝的アルゴリズム(cGA)の並列計算機上での実行は,幅広い問題に対して問題解決環境を提供できる可能性を持っている.代表的な並列cGAとしては,BOAの並列化であるDBOA,PBOA,並列BOA,LINCの並列化であるpLINCなどが存在する.しかし,BOAの並列化はモデルに関する制約やバックトラックを要する.LINCは単純な並列化が可能なものの,大規模な問題に対してもともとの計算量の大きさから,並列計算機上でも大きな計算コストを要する.本論文では,単純に並列化でき比較的少ない計算量で問題構造の検出が可能なD^5と得られた情報に基づいて重複するビルディングブロックを組み合わせることができる交叉手法CDCを用いたD^5-GA+CDCの並列化に取り組む.また,並列D^5-GA+CDCや他の並列cGAの性質を明らかにするために比較実験を行なう.
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 67 (128) 171 -174 2007年12月20日 [査読無し][通常論文]
     
    事前知識によらずに自動的に問題構造を検出するコンペテント遺伝的アルゴリズム(cGA)の並列計算機上での実行は,幅広い問題に対して問題解決環境を提供できる可能性を持っている.代表的な並列cGAとしては,BOAの並列化であるDBOA,PBOA,並列BOA,LINCの並列化であるpLINCなどが存在する.しかし,BOAの並列化はモデルに関する制約やバックトラックを要する.LINCは単純な並列化が可能なものの,大規模な問題に対してもともとの計算量の大きさから,並列計算機上でも大きな計算コストを要する.本論文では,単純に並列化でき比較的少ない計算量で問題構造の検出が可能なD^5と得られた情報に基づいて重複するビルディングブロックを組み合わせることができる交叉手法CDCを用いたD^5-GA+CDCの並列化に取り組む.また,並列D^5-GA+CDCや他の並列cGAの性質を明らかにするために比較実験を行なう.
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会論文誌数理モデル化と応用(TOM) 48 (15) 23 -33 2007年10月15日 [査読無し][通常論文]
     
    遺伝的アルゴリズムによる効率的な探索のために, 同一のビルディングブロック(building block,BB)を構成する遺伝子座の集合を検出する手法は多く提案されている(Heckendornら).しかしながら,これらの手法から得られたリンケージ情報を利用して効果的に交叉を行う方法については,十分な検討がなされてこなかった.特に重複する BB を持つ問題では Yu ら(2005)の交叉手法のみが知られている.しかし,彼らの手法は BB の重複構造が複雑になったとき,頻繁に BB を破壊し,かつ十分な交叉パターンが得られないために,効率的に機能しない.本論文では,Yu らの手法を拡張し,BB 破壊をできるだけ抑えながら,新たな異なる探索点を与える交叉手法を提案する.提案される手法は,コンテクスト依存交叉(Context Dependent Crossover,CDC)と呼ばれ,与えられた親個体組の値を調査したうえで,交換する遺伝子座を決定する.CDC は,リンケージ同定手法と併用されることで,重複する BB を持つ問題を探索する強力なアルゴリズムを提供する.また,提案手法の性能を確認するために,重複の複雑さが制御可能なテスト関数を設計する.In order to realize effective genetic algorithms, there have been several techniques to identify linkage sets of loci to form a building block (BB) (Heckendorn, et al.). By contrast, the way to realize effective crossover from the linkage information given by such techniques has not been studied enough. Especially for problems with overlapping BBs, a crossover method proposed by Yu, et al. (2005) is the first and only known research. However it cannot perform well for problems with complexly overlapping BBs due to BB disruptions and insufficient variety of crossover sites. In this paper, we propose a crossover method which examines values of given parental strings to determine which variables are exchanged to produce new and different strings without increasing BB disruptions as much as possible. Because the proposed method considers the context of parental strings, it is called context dependent crossover (CDC). Combining a scalable linkage identification technique and the CDC, an effective algorithm for problems with overlapping BBs is provided. Moreover, to test the proposed method, we design test functions with controllable complexity of overlaps.
  • 前田 陽樹, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 64 (43) 13 -16 2007年05月17日 [査読無し][通常論文]
     
    分布推定アルゴリズム(Estimation of Distribution Algorithms, EDA)は、有望な解集団の分布からその分布を表す確率モデルを構築し、構築されたモデルから新しい解を生成するアルゴリズムである。モデルを用いることで変数間の依存関係を考慮することができ、GA困難な問題においても有効である。その反面、モデル構築の計算コストが大きくなってしまうという欠点も持っている。そのような最適化手法の開発が進む一方で、それらの手法と局所探索手法の融合手法も研究されている。そこで本論文では、EDA手法の一つであるBayesian Optimization Algorithm(BOA)に擬似焼き鈍し法(Simulated Annealing, SA)による局所探索を導入した手法について検討する。
  • Asim Munawar, Masaharu Munetomo, Akama Kiyoshi
    1191 -1198 2007年 [査読無し][通常論文]
  • 佐竹 佑太, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. BIO, バイオ情報学 2006 (135) 61 -64 2006年12月21日 [査読無し][通常論文]
     
    Extended Compact Genetic Algorithm (ECGA)は集団の分布を表した確率モデルを構築し,構築したモデルを基に新たな個体を生成するアルゴリズムである.構築したモデルによって,互いに依存する複数の遺伝子を検出することができるため,ECGAは広範囲の最適化問題を解くことができる.ECGAの探索能力をさらに高めるためにECGAに近傍探索法を組み込んだ手法が存在する.しかしながら,もっとも探索能力の高い近傍探索法のうちの1つであるTabu Searchは近傍探索法として用いられてこなかった.そこで,本論文ではTabu SearchをECGAに組み込んだ手法を提案し,その手法の有効性について検討する.
  • 佐竹 佑太, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 62 (135) 61 -64 2006年12月21日 [査読無し][通常論文]
     
    Extended Compact Genetic Algorithm (ECGA)は集団の分布を表した確率モデルを構築し,構築したモデルを基に新たな個体を生成するアルゴリズムである.構築したモデルによって,互いに依存する複数の遺伝子を検出することができるため,ECGAは広範囲の最適化問題を解くことができる.ECGAの探索能力をさらに高めるためにECGAに近傍探索法を組み込んだ手法が存在する.しかしながら,もっとも探索能力の高い近傍探索法のうちの1つであるTabu Searchは近傍探索法として用いられてこなかった.そこで,本論文ではTabu SearchをECGAに組み込んだ手法を提案し,その手法の有効性について検討する.
  • 佐竹 佑太, 棟朝 雅晴, 赤間 清 情報処理学会研究報告 2006 (135) 61 -64 2006年12月21日 [査読無し][通常論文]
  • 佐竹 佑太, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 59 (56) 25 -28 2006年05月25日 [査読無し][通常論文]
     
    確率モデル構築型遺伝的アルゴリズム(Probabilistic Model-Building Genetic Algorithms, PMBGAs)は集団の分布を表した確率モデルを構築し,構築されたモデルを基に新たな個体を生成するアルゴリズムである.PMBGAsは少ない適応度評価回数で広範囲の最適化問題を解くことができるが,モデルを構築するために非常に大きな計算コストを要する.いっぽう,局所探索を導入したPMBGAsでは適応度評価回数は多くなるが,モデル構築にかかるコストを削減できる.本論文では,局所探索を導入したPMBGAsにおける適応度評価回数とモデル構築にかかるコストの関係について検討する.
  • 斉藤 雄介, 棟朝 雅晴, 赤間 清 情報処理学会研究報告 = IPSJ SIG technical reports 2006 (20) 103 -108 2006年02月27日 [査読無し][通常論文]
     
    本論文では、等価変換による計算モデルに基づく、並列プログラム生成の理論を提案する。この理論では、与えられた問題を表現する確定節集合を変換するための等価変換ルールの集合から、正当な並列プログラムが生成される。この手法の正当性について説明し、また、ある制約充足問題を解く並列プログラムを使用して簡単な実験を行い、その有効性を示す。
  • 斉藤 雄介, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. ARC,計算機アーキテクチャ研究会報告 167 (20) 103 -108 2006年02月27日 [査読無し][通常論文]
     
    本論文では、等価変換による計算モデルに基づく、並列プログラム生成の理論を提案する。この理論では、与えられた問題を表現する確定節集合を変換するための等価変換ルールの集合から、正当な並列プログラムが生成される。この手法の正当性について説明し、また、ある制約充足問題を解く並列プログラムを使用して簡単な実験を行い、その有効性を示す。
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告 = IPSJ SIG technical reports 2005 (93) 65 -68 2005年09月21日 [査読無し][通常論文]
     
    D^5-GA [4]は互いに依存する遺伝を検出し, その情報を利用して探索を行うGAである.従来のD^5-GAでは, 得られた依存関係情報をもとに, 問題変数を同一のビルディングブロックを構成する変数の集合へと分割し, 交叉において同一の集合に属する遺伝子座を同時に交換することで部分解の効果的な交換を促進した.しかしながら, 実際の問題における部分解はしばしば互いに要素を共有すると考えられる.本論文では, D^5-GAをビルディングブロック重複のある問題に適用するために, リンケージ集合の構造を拡張する.また, 得られた問題構造情報を用いて, 重複するビルディングブロックをできる限り(1)少ない破壊で(2)多く交換するためYuら[6]による交叉手法を改良する.
  • 手塚 大, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 53 (20) 9 -12 2005年03月09日 [査読無し][通常論文]
     
    最適化問題を独立に最適化可能な複数の部分問題に分割可能な場合, 各部分問題を独立に最適化することによって効率的に最適化ができる.遺伝的アルゴリズム(CA)による最適化では, この部分問題を構成する遺伝子座の集合をリンケージグループといい, リンケージグループを識別する手洗をリンケージ同定という.本論文では, 実数値CAのリンケージとは何かを明確に定義する.この定義に基づいて直接的にリンケージの識別を行う二つのリンケージ同定法怯, LINC-RとLIDI-Rを提案する.LINC-Rは目的関数の加法分解性, LIDI-Rは差分の符号独立性にもとづいてリンケージの有無を判定する.これらの手法は直接的にリンケージを識別するため, 効率的にリンケージ同定ができる.これらの手法を用いて, リンケージ同定を行い, リンケージグループごとに並列に最適化を行うことで, 従来の手法よりも短時間でより良い解を得られる.
  • 村尾 直哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. ARC,計算機アーキテクチャ研究会報告 162 (19) 67 -72 2005年03月07日 [査読無し][通常論文]
     
    Bayesian optimization algorithm(BOA)は現在の集団分布を推定したベイジアンネットワークによる確率モデルを構築し, 得られたモデルに基づいて次世代集団を形成することで探索を行う最適化アルゴリズムであり, 適切な符号化が保証されないGA困難な問題においても解を求めることができる. しかし, この分布推定にかかる計算コストは問題サイズに依存しており, 問題サイズの増加に対して計算コストが大きく増加することが知られている. これまでの研究では, 生成される確率ネットワークの品質を下げずに並列構築する手法を提案してきた. 本研究では, このネットワーク並列構築に基づく並列BOAを用いて構造エネルギー最小化問題を解くことで, 蛋白質の立体構造予測問を解決し, 提案手法の有効性について検証する.
  • 釘本 健司, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. EIP, [電子化知的財産・社会基盤] 2004 (89) 63 -69 2004年09月02日 [査読無し][通常論文]
     
    次世代のインターネットの基盤ネットワークとして,WDM(Wavelength Division Multiplexing)に基づいたフォトニックネットワーク(WDM-PN)が注目されている.このWDM-PNにおいては,物理トポロジ上に光パスを割り当てることで論理トポロジが構成される.限られた波長を効率良く使って論理トポロジを構成する問題は,波長割当問題と呼ばれ,制約つき組合わせ問題の一つである.本稿では,リンケージ同定を導入した遺伝的アルゴリズムの波長割当問題への適用を試みたので報告する.本アルゴリズムでは,トラフィック全体の遅延の最小化を目的とし,リンケージ同定手法としてLINC(Linkage Identification by Nonlinearity Check)およびLIEM(Linkage Identification with Epistasis Measure)を用いた.計算機シミュレーションにより単純遺伝的アルゴリズムとの比較を行ない,LIEMの効果を確認した.
  • 釘本 健司, 棟朝 雅晴, 赤間 清 情報処理学会研究報告 = IPSJ SIG technical reports 2004 (89) 63 -69 2004年09月02日 [査読無し][通常論文]
     
    次世代のインターネットの基盤ネットワークとして,WDM(Wavelength Division Multiplexing)に基づいたフォトニックネットワーク(WDM-PN)が注目されている.このWDM-PNにおいては,物理トポロジ上に光パスを割り当てることで論理トポロジが構成される.限られた波長を効率良く使って論理トポロジを構成する問題は,波長割当問題と呼ばれ,制約つき組合わせ問題の一つである.本稿では,リンケージ同定を導入した遺伝的アルゴリズムの波長割当問題への適用を試みたので報告する.本アルゴリズムでは,トラフィック全体の遅延の最小化を目的とし,リンケージ同定手法としてLINC(Linkage Identification by Nonlinearity Check)およびLIEM(Linkage Identification with Epistasis Measure)を用いた.計算機シミュレーションにより単純遺伝的アルゴリズムとの比較を行ない,LIEMの効果を確認した.
  • 手塚 大, 棟朝 雅晴, 赤間 清 情報科学技術フォーラム一般講演論文集 3 (1) 55 -56 2004年08月20日 [査読無し][通常論文]
  • 村尾 直哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. ARC,計算機アーキテクチャ研究会報告 157 (20) 169 -174 2004年03月01日 [査読無し][通常論文]
     
    BOA(Bayesian Optimization Algorithm)は,集団における優良個体群の分布推定に基づいて次世代の個体群を生成する手法であり,通常の遺伝的アルゴリズム(Genetic Algorithms, GA)では解くことが困難な問題を効率よく解くことのできる手法として提案されている.しかし,分布推定にかかる計算コストが大きいため,BOAの並列化のための研究が行われている.既存の研究では,この並列BOAに対していくつかの実験を行っているが,並列プロセッサ台数などが少ないなど不十分であると考えられる.本稿では,この並列BOAの性能に関する実験的検証をより詳細に行っていく.また,並列BOAの計算コストを実験的に調査していく.
  • 村尾 直哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 47 (0) 57 -60 2003年12月11日 [査読無し][通常論文]
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 47 (0) 61 -64 2003年12月11日 [査読無し][通常論文]
  • 村尾 直哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 47 (122) 57 -60 2003年12月11日 [査読無し][通常論文]
     
    通常の遺伝的アルゴリズム(Genetic Algorithms, GA)で解くことが困難な問題に対する解法として,リンケージ同定手法やBOA(Bayesian Optimization Algorithm)などが提案されている.しかし,これらのアルゴリズムは有用ではあるが,計算コストが高いという欠点がある.このコストを小さくするための並列化の研究がいくつか行われているが,解くべき問題に対してどの手法が有用であるかが明らかではない.本稿では,近年提案されている並列リンケージ同定と並列BOAを扱い,これらの性能を比較することで,問題の性質から適用すべき手法を選択する基準について検討する.
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 47 (122) 61 -64 2003年12月11日 [査読無し][通常論文]
     
    遺伝的アルゴリズム(GA)においては,互いに依存関係があり同一のビルディングブロックを構成する変数をあらかじめ同定することで,効率的な探索が可能となる.変数間の依存関係を調査する手法としては,値の摂動による適応度の差分を利用する手法や,有望な部分個体群に存在するストリングの持つ値の分布を調査する手法が提案されている.本論文では,これらの両者の特長をあわせもつ手法として,値の摂動による適応度の差分から分類された部分個体群の分布を調査する手法を提案する.提案手法は,より少ない計算量で,正確な依存関係を同定することが可能である.
  • 村尾 直哉, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. HPC,[ハイパフォーマンスコンピューティング] 93 (29) 161 -166 2003年03月11日 [査読無し][通常論文]
     
    近年,並列遺伝的アルゴリズムに関する研究が行われているが,特定の間題に関する性能評価を行ったものが多く,問題の性質と並列化手法との関係についてはあまり知られていない.本論文では,適応度重みに基づいた問題の性質と既存の並列遺伝的アルゴリズムとの関係についての考察を行う.また,提案するリンケージ同定に基づく並列遺伝的アルゴリズムとの比較を行い,与えられた問題に対して適用すべき並列化手法とは何かという,並列遺伝的アルゴリズムを設計するため指針となるものを提示する.
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 110 (108) 73 -78 2002年11月21日 [査読無し][通常論文]
     
    都市圏ネットワークの設計は,地形やトラフィック要求などの制約を満足するネットワーク形状を多くの選択肢のなかから選択しなければならない困難な組み合わせ最適化問題である.ネットワーク設計問題において,単純GAによる探索はしばしばビルディングブロックを適切に組み合わせることができず,失敗する.同一のビルディングブロックに属する遺伝子座をあらかじめ同定し,適切なビルディングブロック交換を考慮したリンケージ同定GAは,問題のより適切な解決が可能にした[7].本論文では,単純な遺伝子座どうしの相互依存関係を考慮した単層型のリンケージ同定をビルディングブロックどうしの相互依存関係を再帰的に定義する階層型のリンケージ同定遺伝的アルゴリズムを用いる手法へと拡張し,さらに低コストなネットワークの設計を目指す.
  • 辻 美和子, 棟朝 雅晴, 赤間 清 情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 39 (36) 9 -12 2002年05月10日 [査読無し][通常論文]
     
    遺伝的アルゴリズムにおいてはビルディングブロックとなる遺伝子をストリング上で密に符号化することが重要である。しかし,ネットワーク設計問題では地形,通信要求,経路などさまざまな要素が互いに複雑に影響するため,適切な符号化を行なうことは難しい.多くの既存研究はビルディングブロックの密な符号化について考慮しておらず,これを考慮していたとしても地理的な要素のみである.本論文では,遺伝子の値の摂動による適応度の変化を用いて問題に関する前知識なしにビルディングブロックの位置であるリンケージを同定する手法であるLIEM(Linkage Identication with Epistasis Measure)を導入し,ビルディングブロックを効率的に組み合わせ,遺伝的アルゴリズムによる効果的な解の探索を実行する.実験を行ない,本論文による手法で設計されたネットワークと幾つかの交叉手法,符号化手法による単純遺伝的アルゴリズムによって設計されたネットワークの敷設コストを比較しLIEMによるネットワーク設計の有用性を証明する.
  • 小林 英博, 棟朝 雅晴, 赤間 清, 佐藤 義治 マルチメディア通信と分散処理ワークショップ論文集 2000 (15) 91 -96 2000年12月06日
  • 小林 英博, 棟朝 雅晴, 赤間 清, 佐藤 義治 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 100 (102) 7 -12 2000年05月26日 [査読無し][通常論文]
     
    ネットワーク資源は有限であり、特に高速で帯域幅の大きなリンクは高価である。よって帯域幅を効率よく割り当てることによって得られる利益は大きく、有限の資源を無駄なく使用するためには帯域幅割当アルゴリズムが重要となる。これまで遺伝的アルゴズムを用いたネットワーク帯域幅割当のためのアルゴリズムとしてGRA(Genetic Routing Algorithms)が提案されているが、これは集中型のアルゴリズムでありネットワーク障害が発生した場合には割り当てが不可能となる。そこで筆者らはGRAを分散化したD-GRA(Distributed GRA)を提案したが、D-GRAは単なる分散化に留まっており、障害回復処理やリンク障害に対して不十分な点が残されている。そこで本研究では、D-GRAを改善し、リンク障害の回復に対応したアルゴリズムを提案する。
  • 山口 直彦, 棟朝 雅晴, 赤間 清, 佐藤 義治 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 100 (102) 69 -74 2000年05月26日 [査読無し][通常論文]
     
    インターネットに代表されるように、ネットワークのサイズは年々増加の一途を辿っており、その上を流れるデータ量についてもまた、同様に増加を続けている。そこで、増え続けるネットワーク上のトラフィックへの対応策として、複数の代替経路を用いて負荷を分散させることにより、ネットワーク資源を効率的に使用し、遅延を改善することが可能である。このような経路制御アルゴリズムについては、これまでに遺伝的アルゴリズムを用いた負荷分散の手法が提案されているが、そこでは、ネットワーク中の各ノードが遺伝的操作によって複数の代替経路を生成し、それらの代替経路間でリンクの負荷に応じて動的に負荷の分散を行なう。本論文では、経路の評価方法に焦点をあて、評価の手法や頻度を変更することにより、ネットワークにどのような影響を与えるかを調べる。
  • 山口 直彦, 棟朝 雅晴, 佐藤 義治 第60回全国大会講演論文集 2000 (1) 449 -450 2000年03月14日
  • 遺伝的アルゴリズム4<分担 : 北野 宏明 編>
    産業図書 2000年 [査読無し][通常論文]
  • 小林 英博, 棟朝 雅晴, 佐藤 義治 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 95 (94) 91 -96 1999年05月27日 [査読無し][通常論文]
     
    大規模なネットワークにおいてはネットワーク資源を効率良く使用するための帯域幅割り当て(Bandwidth allocation)が求められるが、割り当て問題は組合せ最適化問題であり高速に最適解を得ることが困難である。この問題に対しMario Gerla[1]らは、平均パケット遅延を目的関数とした解法を提案している。本研究では、Mario Gerla[1]らの平均パケット遅延に基づいた解法を改良し、平均パケット遅延を小さくすると同時に各リンクに対するばらつきを小さくするようなトラフィックの割り当てを行なう多目的最適化を試みる。そこで多目的最適化向けに設計された遺伝的アルゴリズムを適用する。遺伝的アルゴリズムを適用した多目的最適化の解法は数種類考えられているが、パレート最適解を適用して最適解を求める。また、遺伝的アルゴリズムを適用する場合にはパレート最適解を適切に評価・選択することが必要であり、この点に関しての手法を提案する。
  • 山口 直彦, 棟朝 雅晴, 佐藤 義治 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 95 (94) 97 -102 1999年05月27日 [査読無し][通常論文]
     
    本稿では、自律システム(Autonomous System)間の通信において、進化的手法を用いて代替経路のリストを生成し、それらの間で通信パケットを分配することによって負荷の分散を図る適応型ルーティングアルゴリズムを提案する。AS間ルーティングとして広く知られるBGP(Border Gateway Protocol)で用いられているルーティングアルゴリズムでは、等しい距離をもつ代替経路間ではパケットを分散できるが、現在の負荷状態に応じた動的な経路決定は行っていない。本稿で提案するGIAR(Genetic Inter AS Routing)アルゴリズムは、リンクの負荷状態を観測し、代替経路間で確率的にパケットを分配することで負荷の分散を実現する。AS間ルーティングで安定した観測を達成するために、threshold policyを用いて、待ち行列に基づくリンクの負荷状態を分類を行う。
  • MUNETOMO Masaharu Proceedings of the 1999 Genetic and Evolutionary Computation Conference 1999年
  • 森口 秀一, 棟朝 雅晴, 佐藤 義治 全国大会講演論文集 56 (0) 58 -59 1998年03月17日 [査読無し][通常論文]
  • M Munetomo, Y Takai, Y Sato 1998 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-5 2774 -2779 1998年 [査読無し][通常論文]
     
    This paper presents a string migration scheme for an adaptive network routing algorithm called a genetic routing algorithm[10] which employs genetic operators to create alternative routes in a routing table. String migrations are employed usually in islands model of parallel or distributed genetic algorithms, which exchange strings among subpopulations to accelerate their convergence. We propose a tailored version of string migration for the genetic routing algorithm in order to realize effective information exchanges among nodes to have optimal route with less communication overhead in the network.
  • MUNETOMO Masaharu Technical Report IlliGAL Report 1998年
  • MUNETOMO Masaharu Technical Report IlliGAL Report 1998年
  • 冨川 裕樹, 高井 昌彰, 棟朝 雅晴, 山本 強 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 85 (104) 133 -136 1997年11月06日 [査読無し][通常論文]
     
    インターネットなどのWANを介して交渉する場合、WANはネットワークの遅延が大きく、また現在のインターネットのトラフィック増大にともない、常に安定した通信ができるとは限らない。モバイルエージェントはネットワーク上を移動可能なプログラムであり、プログラム実行中に動的に計算機間を渡り歩くことができ、移動した先で他のエージェントとローカルに対話することが可能であることから、WANを介した交渉に適すると考えられる。本論文では、モバイルエージェントを会議開催日時決定の支援へ応用する枠組みを提案する。そして実際に簡単なシステムをインプリメントし、より有効なシステムを目指すためにはどのようなエージェントの能力が必要となるかについて考察する。
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会研究報告. マルチメディア通信と分散処理研究会報告 80 (13) 205 -210 1997年01月30日 [査読無し][通常論文]
     
    本論文では、代替経路間の負荷分散機構を有する適応型ルーテイング手法を提案し、その有効性をシミュレーション実験により示す。従来用いられてきたルーテイング手法はルーティングテーブルやリンクの状態をブロードキャストするため、ネットワークが大規模化した場合に多くの通信コストを要することが予想される。本論文で提案するルーティングアルゴリズムは、実際に多数のパケットが使用している経路に関してのみ代替経路の生成およびその通信遅延時間の評価を行うため、ルーティングのための,情報交換に必要な通信コストを大きく削減することが可能となる。本手法においては、遺伝的アルゴリズムを使用することで代替経路のリストを生成するとともに、それらの間で通信バケットを分配することで負荷分散を実現する。ネットワーク通信をシミュレーションするシミュレータを用いた評価実験を行い、従来手法と比較して、少ない通信コストにより効果的なルーティングが実現されていることを示した。
  • 村井 康紀, 棟朝 雅晴, 高井 昌彰 情報処理学会研究報告. DPS,マルチメディア通信と分散処理研究会報告 79 (108) 43 -48 1996年11月14日 [査読無し][通常論文]
     
    近年コンピュータネットワークの世界的な規模拡大に伴い、通信経路を決定するルーテイングが重要性を高めている。本稿では遺伝的アルゴリズムの考えを導入したルーテイングアルゴリズムを提案する。提案手法はパケットの伝送遅延時間を観測することでネットワークの状態変化に適応し、動的に経路を変更し、始点経路制御を行う。ネットワーク上の各ルータは、経路を符号化した遺伝子集団を有し、個々の遺伝子の適合度はその経路の平均伝送遅延時間で与えられる。シミュレーションにより提案手法が比較的規模の大きなネットワークに対しても有効に機能することを確認した。さらに各ルータにおける遺伝子集団の初期値を変化させて実験を行った結果、提案手法の性能は初期値に大きく依存することが分かった。
  • 村井 康紀, 棟朝 雅晴, 高井 昌彰 全国大会講演論文集 52 (0) 121 -122 1996年03月06日 [査読無し][通常論文]
     
    計算機ネットワークの拡大とトラヒックの増大に伴い、通信経路を決定するルーティング手法が急速にその重要性を高めている。本稿では遺伝的アルゴリズムを応用して、ネットワーク状態の変化に適応し、動的に経路選択を行うルーティング手法を提案する。経路選択の目的は平均の通信遅延時間を最小にすることであるが、これに要する付加的な制御情報の通信もネットワークのトラヒックに影響を与えるため、その通信は最小限に押さえられる必要がある。
  • 池田 真樹, 棟朝 雅晴, 高井 昌彰 全国大会講演論文集 52 (0) 161 -162 1996年03月06日 [査読無し][通常論文]
     
    分散システムの利用率を向上させるためには、システムを構成する計算機間で負荷を平均化する必要がある。動的負荷分散アルゴリズムは負荷の重い計算機から負荷の軽い計算機へタスクを転送することでシステム全体として負荷の平均化をはかる。少ない通信量で効果的なタスク転送を行なうために、タスク転送要求の送出先を複数指定するマルチキャストを導入した手法が提案されている。 一方、局所メモリを持つ自立した計算ノードが専用の高速通信ネットワークにより相互結合されたMIMD型の並列計算機である超並列計算機は、高速な並列計算機を安価に実現するアーキテクチャとして近年注目を集めており、数多くの開発例が存在する。 そこで本論文では、マルチキャストによる動的負荷分散アルゴリズムを超並列計算機へ実装し、そのアルゴリズムの性能評価を行なうことで、超並列計算機上でのアルゴリズムの特性を調べる。具体的には、マルチキャストを用いた動的負荷分散アルゴリズムのシミュレータをParallel-Ware(ExPress)の通信ライブラリを用いて超並列計算機SR-2001上に実現し、シミュレーション実験を通してアルゴリズムの性能評価を行なう。
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 電子情報通信学会論文誌. D-2, 情報・システム 2-情報処理 79 (2) 230 -238 1996年02月25日 [査読無し][通常論文]
     
    確率的な環境への適応学習を行う場合, 確率学習オートマトンに代表される強化学習が一般に用いられるが, 選択可能な行動の数が多くなった場合に最適解への収束が著しく遅くなるという欠点がある. 本論文では遺伝的アルゴリズムを応用することで, 強化学習における収束速度の問題点を解消する手法を提案する. 提案するアルゴリズムStGA(Stochastic Genetic Algorithm)においては, すべての可能な行動の中から少数の行動を集団としてサンプリングし, その集団に対して確率学習オートマトンを適用することで強化学習の収束速度を向上させる. 更に, 遺伝的操作を用いて集団内に含まれていない新たな行動を生成することを通して集団の内容を更新し, 最適な行動を効率良く探索する. StGAの収束性を証明するため, 確率学習オートマトンのε-optimalityをもとにした理論的解析を行う. 更にシミュレーション実験により, 可能な行動の数が多い場合におけるStGAの有効性を示す.
  • 冨川 裕樹, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会研究報告. 人工知能研究会報告 95 (105) 25 -30 1995年11月07日 [査読無し][通常論文]
     
    確率学習オートマトンによる学習では、可能な戦略の数が多い場合に収束が遅くなるという問題点がある。この問題点を解消するために、SLAに遺伝的アルゴリズムの手法を取り入れた、確率学習機構を有する遺伝的アルゴリズム(StGA)が提案されている。本論文ではStGAをゲームの戦略学習のための手法として応用することを考え、エージェントが多対多で対戦を行うゲームへの適用を行った。それぞれのエージェントは非明示的な通信を行うものとし、通信メッセージの意味を事前には与えない。このような条件のもとでシミュレーション実験を行い、エージェント間における協調戦略の発現について論じる。
  • 山下 貴幸, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 全国大会講演論文集 50 (0) 249 -250 1995年03月15日 [査読無し][通常論文]
     
    複数の計算機をLANで接続して資源の共有を図る分散システムにおいて、計算機間で負荷の分散を行うことにより、応答時間の短縮や資源利用率の改善など、システム性能の向上を図ることができる。この目的のため、種々の負荷分散方式が提案されてきた。負荷分散方式は、静的負荷分散方式と動的負荷分散方式に分類することができる。さらに、動的負荷分散は、負荷情報の管理とタスク転送の決定を一台の計算機で行う集中制御型と、各計算機で独立して行う分散制御型に分けられる。本研究では[3]を基に、マルチキャストによるタスク転送要求の送出先の決定に対して遺伝的アルゴリズムを適用することで、より効率的な負荷情報の収集と利用を図る分散制御型動的負荷分散方式を提案する。また、UNIXネットワークで構成される分散システム上に実装し、模擬タスクを用いたシミュレーション実験により性能評価を行う。
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 全国大会講演論文集 50 (0) 285 -286 1995年03月15日 [査読無し][通常論文]
     
    本稿ではエリート戦略を有する遺伝的アルゴリズム(Genetic Algorithms,GA)に関して、非斉次マルコフ連鎖を用いた解析を行う。GAの収束性に関しては、マルコフ連鎖を用いた解析が従来行われてきたが、本論文では、非斉次マルコフ連鎖の遷移行列を用い、より簡明な収束性の証明を行う。さらにその結果を用いて、大域的最適解を得る確率に関する収束速度の下限を求めた。
  • 冨川 裕樹, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会研究報告. 人工知能研究会報告 95 (23) 85 -90 1995年03月06日 [査読無し][通常論文]
     
    本論文では、集団対集団で対戦を行う集団対戦型ゲームの戦略学習を議論する。集団対戦型のゲームにおいては、集団内の個々のエージェントがそれぞれ別々の戦略を取る場合に、それらを組み合わせた集団全体としての可能な戦略の組合せが非常に多くなる。そこで、我々は確率学習による適合度評価を行う遺伝的アルゴリズムStGA(Stochastic Genetic Algorithm)を用いることで効率的な学習の実現を試みる。StGAでは、可能な全戦略の中から少数の戦略をサンプリングし、それに対して確率学習および遺伝的操作を適用する。シミュレーションによる比較実験を通して、StGAの集団対戦型ゲームにおける学習手法としての有効性を検証する。
  • 富川 裕樹, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 北海道大学工学部研究報告 (172) p15 -22 1995年02月
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会研究報告. マルチメディア通信と分散処理研究会報告 94 (105) 31 -36 1994年12月02日 [査読無し][通常論文]
     
    本論文では,負荷状態の観測とタスク転送先の決定を遺伝的操作により学習する動的負荷分散の一手法を提案する.その前提として,分散システムにおけるノードをFIFOおよびRound-Robin待ち行列により構成されるものと仮定し,その内部状態についてモデル化を行う.動的負荷分散では,タスクを負荷の重いノードから負荷の軽いノードへと転送することで負荷の均一化を図るが,負荷の軽いノードを発見するためには通信ネットワークを介した転送要求の送出が必要となる.この要求をランダムまたはブロードキャストにより送出した場合,無駄な要求が多数送られることが予想される.提案する手法ではマルチキャストにより特定のノード群に対し要求を送出し,その送出先のリストを遺伝的アルゴリズムの個体として学習を行う.
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 全国大会講演論文集 49 (0) 231 -232 1994年09月20日 [査読無し][通常論文]
     
    従来の遺伝的アルゴリズム(Genetic Algorithms,以下GAと略す)では、正確な適合度値が必要なときに必要な数だけ求められることを暗黙の前提としている。しかし、実際の問題へ応用する場合、適合度評価に時間を要し、一度に多くの適合度値を計算することが現実的でないことがある。また、確率的な環境への適応学習などの場合、環境から得られる情報は、ある行動の成功・失敗の2値で示されるため、適合度の値として直接採用することはできない。本論文では、逐次的に適合度評価を行なうことで、確率的な環境に適応する遺伝的アルゴリズムStGA(Stochastic Genetic Algorithm)を提案する。StGAでは適合度の評価に確率学習オートマトン(Stochastic Learning Automata,SLA)を採用した。これにより、環境から得られる情報が成功・失敗の2値に限られ、かつ逐次的にしか評価値が得られない場合でも、適切な適合度値の分布を集団内に作り出す。また、StGAをSLAの改良とみなすこともできる。SLAには、状態空間のサイズが非常に大きな場合に、収束が著しく遅くなるという欠点がある。この欠点を改善するために、従来、連想記憶を用いた状態空間の圧縮などの対策が講じられてきたが、問題に依存した静的な方法であることから一般に広く用いることはできない。StGAでは、状態空間をGAの個体の形にコーディングし、集団という形で状態空間からサンプリングを行なって、それに対して遺伝的操作を適用することにより、問題に適応する形で状態空間の圧縮を実現することができる。本論文では、SLAのみの場合とシミュレーション実験により比較検討することを通して、GAによる状態空間の圧縮が収束性の向上に大きな効果があることを示す。
  • 冨川 裕樹, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 全国大会講演論文集 49 (0) 233 -234 1994年09月20日 [査読無し][通常論文]
     
    従来の遺伝的アルゴリズム(Genetic Algorithm,以下GAと略す)を、適合度値の評価に時間を要する問題や確率環境への適応学習に適用することは困難である。このような問題に対して、確率学習による適合度評価機構を有する遺伝的アルゴリズムStGA(stochastic Genetic Algorithm)が提案されている。StGAでは、適合度の評価に確率学習オートマトンSLA(stochastic Learning Automata)を用いている。SLAには、状態空間のサイズが非常に大きい場合に収束が著しく遅くなるという欠点がある。StGAはこの点を改善し、問題に適応する形で状態空間を圧縮することを目的としている。我々はStGAが状態空間の圧縮を行なうという点に着目し、これを戦略の種類が非常に多いゲームにおける戦略の獲得に応用できるのではないかと考えた。本論文では、StGAとSLAをゲームにおける戦略の獲得を行なう手段としてインプリメントして対戦を行ない、状態空間のサイズが大きい場合におけるStGAの有効性の検証を行なう。
  • 山下 貴幸, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 全国大会講演論文集 49 (0) 251 -252 1994年09月20日 [査読無し][通常論文]
     
    複数の計算機をLANで接続して資源の共有を図る分散システムにおいて、計算機間で負荷の分散を行うことにより、応答時間の短縮や資源利用率の改善など、システム性能の向上を図ることができる。この目的のため、種々の負荷分散方式が提案されてきた。分散制御型の動的負荷分散方式に遺伝的操作を導入した手法として、遺伝的アルゴリズムと確率学習オートマトンによる動的負荷分散(GeSLA)に関する研究が行われている。この手法においては、タスク転送をどの計算機に対して要求するかを記述した文字列を遺伝的アルゴリズム(Genetic Algorithms,GA)における個体とし、その適合度値の更新に確率学習オートマトン(Stochastic Learning Automata,SLA)による確率的山登り法を適用している。本研究では、UNIXワークステーションをLANで接続した分散システム上にこの方式を実装し、実際に生成したタスクを用いた実験により性能評価を行う。
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会論文誌 35 (9) 1815 -1827 1994年09月15日 [査読無し][通常論文]
     
    本論文では集団分割に基づく並列遺伝的アルゴリズムにおいて,効率的な個体交換を行う交換アルゴリズムを提案する.集団分割による並列遺伝的アルゴリズムは,個体からなる集団をいくつかの部分集団に分割し,それぞれを並列計算機のプロセッサに割り当てて遺伝的アルゴリズムを実行することにより,中粒度の並列処理を実現するものである.この手法においては集団の一様化による探索効率の減少を防ぐために部分集団間で通信ネットワークを介した個体交換を行う必要がある.マルチプロセッサシステムにおいてプロセッサ間通信量を減少させることがその性能を向上させる上で重要であるが,並列遺伝的アルゴリズムに関する従来の研究では,個体の交換がその必要性とは関わりなく一定世代ごとまたは一定確率で行われており,並列処理の効率が悪いと考えられる.本論文で提案する個体交換アルゴリズムSigma-Exchangeは各部分集団内の適合度分布を観測し,適合度分布の標準偏差の値が一定割合減少した場合にのみ交換の手続きを起動することにより,少ないプロセッサ問通信でより精度の高い解を速く得ることを目的としている.提案する手法の有効性を示すために,非同期のメッセージ受渡しによる中粒度並列計算機であるマルチコンピュータネットワークを前提としたシミュレーション実験を行った.その結果,代表的な組合せ最適化問題について,提案する手法が有効であることが...
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会研究報告. 人工知能研究会報告 94 (20) 95 -102 1994年03月08日 [査読無し][通常論文]
     
    分散計算システムは自律した計算機が比較的通信遅延の大きい通信ネットワークを介して相互結合されたシステムである.分散計算システムの性能向上のためには,それぞれの計算機における負荷の一様化をはかることが重要である.分散制御型の動的負荷分散アルゴリズムは計算の実行中にそれぞれの計算機で負荷状態の観測を行ない,負荷の重い計算機から軽い計算機へタスクの転送を行なうことで負荷を一様化する.本論文では,確率学習オートマトンと遺伝的アルゴリズムを用いることで効率的なタスク転送要求の送出法を学習する分散制御型の動的負荷分散アルゴリズムを提案する.本手法では,それぞれの計算機ごとにタスク転送をどの計算機に対して要求するかを記述した文字列からなる集団を用意する.そして,その集団に対して確率学習オートマトンと遺伝的アルゴリズムの操作を用いた学習を適用することで効率的な転送要求の送出を行なう.シミュレーション実験により提案する手法の有効性が確かめられた.
  • 棟朝 雅晴, 高井 昌彰, 佐藤 義治 北海道大学工学部研究報告 167 (167) p127 -135 1994年01月 [査読無し][通常論文]
  • 高橋 正和, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 情報処理学会研究報告. 人工知能研究会報告 93 (103) 9 -16 1993年11月24日 [査読無し][通常論文]
     
    遺伝子集団分割による並列遺伝的アルゴリズムモデルは,分割された部分集団を並列計算機の各プロセッサに割当て,遺伝的アルゴリズムを実行する.本論文では,部分集団に関する遺伝的操作パラメータ群を動的に変化させ,効率的な解空間探索を行なうモデルを提案する.本モデルは,遺伝的操作パラメータを遺伝子集団のメタレベルに配置し,そのパラメータを最適化するという論理的な階層構造を持ち,各プロセッサ内の遺伝子情報を相互交換する事により,解空間を部分集団内で協調的に探索する.さらに,分散環境であるUNIX-Network上に本モデルを実現し,実験による評価を行なった.
  • 高橋 正和, 棟朝 雅晴, 高井 昌彰, 佐藤 義治 全国大会講演論文集 46 (0) 301 -302 1993年03月01日 [査読無し][通常論文]
     
    遺伝的アルゴリズムは、生物の遺伝子の働きにヒントを得た最適化手法である。問題の対する多数の解候補を遺伝子の形にコーディングし、その適応度の高いものが増加してゆく「淘汰」(selection)2つの遺伝子内の部分情報を交換する「交叉」(crossover)、ある小さな確率で遺伝子内の情報が変化する「突然変異」(mutation)の基本3操作を一世代とし、それを繰り返すことによって近似最適解を得ようとするアルゴリズムである。しかし、一般的にコーディングやcrossover方法の設定に関しては、ビルディングブロック仮説を満たす必要がある。しかしながら。問題によってはこの仮説を常に満たすようなコーディング方法を求めることが困難な場合がある。その為、最適解に収束しない事も少なくない。そこで本稿では、コーディングを動的に変化させるadaptive codingを提案しナップザック問題を用いた数値実験によりその有効性を確認する。
  • 棟朝 雅晴, 高井 昌彰, 佐藤義治 情報処理学会研究報告アルゴリズム(AL) 1992 (58) 41 -48 1992年07月17日 
    遺伝子集団分割による並列遺伝的アルゴリズムにおける遺伝子交換アルゴリズムの改良とその評価を行なった結果について述べる。遺伝子集団の中に含まれるスキーマ数の減少を、その適合度の分布の標準偏差を計算することで間接的に評価し、遺伝子交換を行なう基準とすることで、遺伝子集団の中に含まれているスキーマの数の急速な減少を防ぎ、遺伝的アルゴリズムのスキーマ処理効率を維持する。そのために標準偏差と遺伝子集団内に含まれるスキーマの数について、Sigma?Hypothesisと呼ばれる仮説を立て、理論的解析とシミュレーション実験によりこれを検証した。さらに、この仮説に基づく遺伝子交換アルゴリズムについて、その有効性を実験により確認した。Improvement of exchange algorithms on parallel genetic algorithms and their evaluation are presented in this paper. To avoid rapid decrease of the number of schemata in a population and maintain efficient schema processing, the algorithm presented estimates indirectly the decrease of the number of schemata by using standard deviation of fitness distribution. We propose sigma-hypothesis and discuss its validity through some theoretical and empirical results. A parallel genetic algorithm based on the hypothesis is presented and some experiments are made to confirm its efficiency.

書籍等出版物

  • 吉岡 信和, 棟朝 雅晴, 本橋 賢二, 西村 一彦, 谷沢 智史, 横山 重俊 (担当:共著)
    インプレスR&D 2012年08月 210
  • Advances in Grid Computing
    Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama (担当:分担執筆範囲:pp.19-28)
    2011年
  • 棟朝 雅晴 (担当:単著)
    森北出版 2008年07月 (ISBN: 4627847815) 160
  • Advances in Evolutionary Algorithms
    Mohamed Wahib, Asim Munawar, Masaharu Munetomo, Kiyoshi Akama (担当:分担執筆範囲:pp.315-334)
    IN-TECH 2008年
  • Linkage in Evolutionary Computation
    Asim Munawar, Mohamed Wahib, Miwako Tsuji, Masaharu Munetomo, Kiyoshi Akama (担当:分担執筆範囲:pp.159-187, pp.441-459)
    Springer 2008年
  • Computational Intelligence Paradigms – Innovative Applications
    Miwako Tsuji, Masaharu Munetomo (担当:分担執筆範囲:pp.251-280)
    Springer 2008年
  • 統計データ科学事典
    棟朝雅晴 (担当:分担執筆範囲:遺伝的アルゴリズム)
    2007年
  • Evolutionary Computation in Dynamic and Uncertain Environments
    Masaru Tezuka, Masaharu Munetomo, Kiyoshi Akama (担当:分担執筆範囲:pp.417-436)
    2007年
  • 遺伝的アルゴリズム4
    棟朝雅晴 (担当:分担執筆範囲:第9章:遺伝的アルゴリズムによる適応ルーティング)
    産業図書 2000年 (ISBN: 4782851499)
  • Telecommunications Optimisation: Heuristic and Adaptive Methods
    Masaharu Munetomo (担当:分担執筆範囲:pp.151-166)
    John Weily & Sons 2000年
  • Computational Intelligence in Telecommunication Networks
    Masaharu Munetomo (担当:分担執筆範囲:pp.287-302)
    CRC Press 2000年

講演・口頭発表等

  • Optimal Feature Selection for Intrusion Detection Systems Employing Multi-Objective Genetic Algorithm  [通常講演]
    Chang Geng, Masaharu Munetomo
    2018 JPNSEC International Workshop on Evolutionary Computation 2018年08月 口頭発表(一般)
  • 森川達矢, 保田俊行, 大倉和博, 松村嘉之, 棟朝雅晴
    計測自動制御学会システムインテグレーション部門講演会(CD-ROM) 2015年12月
  • 阿部友哉, 棟朝雅晴
    計測自動制御学会システム・情報部門学術講演会講演論文集(CD-ROM) 2015年11月
  • 中野翔, 渡邉真也, 千葉一永, 金崎雅博, 棟朝雅晴
    計測自動制御学会システム・情報部門学術講演会講演論文集(CD-ROM) 2015年11月
  • 玉家武博, 斎藤篤志, 三浦克宜, 棟朝雅晴
    情報処理学会全国大会講演論文集 2015年03月
  • 倉田優太, 金崎雅博, 千葉一永, 渡邉慎也, 棟朝雅晴
    数値流体力学シンポジウム講演論文集(CD-ROM) 2015年
  • 分散クラウドシステムにおける遠隔連携技術  [招待講演]
    棟朝 雅晴
    学際大規模情報基盤共同利用・共同研究拠点 第1回ネットワーク型学際研究シンポジウム 2014年03月
  • インターネット上のデータ利活用を促進するための人間ベース遺伝的アルゴリズム  [通常講演]
    幸田里奈, 長谷部良輔, 大西圭, 棟朝雅晴
    第6回進化計算学会研究会 2014年03月
  • アカデミッククラウドにおけるCloudStackの活用事例と今後の展望  [招待講演]
    棟朝 雅晴
    CloudStack Day Japan 2014 2014年03月
  • 研究支援に係るアカデミッククラウドの調査検討  [通常講演]
    棟朝 雅晴
    平成25年度国家課題対応型研究開発推進事業『アカデミッククラウド環境構築に係るシステム研究』提案「コミュニティで紡ぐ次世代大学ICT環境としてのアカデミッククラウド」最終報告会 2014年02月
  • 研究支援に係るアカデミッククラウド  [通常講演]
    棟朝 雅晴
    大学ICT推進協議会年次大会「コミュニティで紡ぐ次世代大学ICT環境としてのアカデミッククラウド」事業中間報告 2013年12月
  • 研究支援のためのアカデミッククラウド  [通常講演]
    棟朝 雅晴
    アカデミッククラウドシンポジウム2013 2013年09月
  • 田中一真, 棟朝雅晴, 赤間清
    全国大会講演論文集 2013年03月 
    複数天体の重力支援を利用した宇宙探査機の軌道最適化は,厳密解の発見が困難な,制約付き非線形多変数関数の最適化問題である.本研究では,欧州宇宙機関で公開されている軌道最適化問題を単峰性正規分布交叉を用いた実数値遺伝的アルゴリズムによって解く.
  • 平島慶典, 三浦克宜, 棟朝雅晴
    全国大会講演論文集 2013年03月 
    本研究では、与えられた論文に対して、的確な研究分野を判定するためのツールを開発する。研究を発展させる上で、関連研究のサーベイは重要であり、そのためには論文の適切な研究分野を知ることは極めて大切である。適切な研究分野を発見する方法として過去の論文と照らし合わせる方法が考えられる。しかしそれには膨大な計算量が掛かるため、逐次処理ではコストがかかる。この問題を解決するために、並列計算を使用している。研究分野の位置づけを行うために、本論文ではMahoutによるクラスタリングを行っており、そのための計算は、Hadoopを利用した並列計算を使用している。
  • クラウドコンピューティングの最新動向  [招待講演]
    棟朝 雅晴
    OR学会北海道支部講演会 2013年02月
  • 北海道大学アカデミッククラウドの活用事例  [招待講演]
    棟朝 雅晴
    学術情報基盤オープンフォーラム「大学クラウド活用における、検証と課題と対策」 2013年02月
  • 北海道大学アカデミッククラウドのご紹介とクラウド技術の最新動向,研究動向について  [招待講演]
    棟朝 雅晴
    第2回デバイスとクラウドの高度融合による新事業創出研究会 2013年01月
  • リンケージツリー遺伝的アルゴリズムにおける計算量削減の検討  [通常講演]
    鈴木一史, 棟朝雅晴
    進化計算シンポジウム2012講演論文集 2012年12月
  • スワームロボットシステムにおける大規模並列計算環境を用いた分散型CMA-ESの実装  [通常講演]
    竹中貴治, 保田俊行, 大倉和博, 松村嘉之, 棟朝雅晴
    進化計算シンポジウム2012講演論文集 2012年12月
  • クラウド環境における進化計算用グリッドサービスの並列化効率の評価  [通常講演]
    藤田二夫, 保田俊行, 大倉和博, 松村嘉之, 伍賀正典, 棟朝雅晴
    進化計算シンポジウム2012講演論文集 2012年12月
  • 相澤孝至, 棟朝雅晴
    情報処理北海道シンポジウム講演論文集 2012年10月
  • 萩田克美, 棟朝雅晴, 上島豊, 大宮学
    計算工学講演会論文集(CD−ROM) 2012年05月
  • Hokkaido University Academic Cloud: Largest Academic Cloud System in Japan  [招待講演]
    Masaharu Munetomo
    Cloud Technical Leadership Forum 2012年05月 口頭発表(招待・特別)
  • 萩田 克美, 棟朝 雅晴, 上島 豊
    計算工学講演会論文集 Proceedings of the Conference on Computational Engineering and Science 2012年05月
  • 北海道大学アカデミッククラウドの構築とサービスについて  [招待講演]
    棟朝雅晴
    アカデミッククラウドワークショップ2012@広島 2012年02月 口頭発表(基調)
  • 北海道大学における大規模学術クラウドの構築と運用について  [招待講演]
    棟朝雅晴
    サイエンティフィック研究会システム技術分科会第2回会合 2012年01月 口頭発表(招待・特別)
  • 北海道大学アカデミッククラウドの構築と運用について  [招待講演]
    棟朝雅晴
    グリッド協議会第33回ワークショップ 2011年12月 口頭発表(基調)
  • 北海道大学アカデミッククラウド〜国内最大規模の学術クラウドについて  [招待講演]
    棟朝雅晴
    Open Cloud Conference 2011 in Sapporo 2011年12月 口頭発表(基調)
  • Estimation of Distribution Algorithms without Explicit Selections  [招待講演]
    Masaharu Munetomo
    The 8th World Multi-Conference on Systemics, Cybernetics and Informatics 2004年 口頭発表(招待・特別)
  • Linkage Identification by Non-monotonicity Detection for Overlapping Functions  [招待講演]
    Masaharu Munetomo
    Journal Showcase at the 2000 Genetic and Evolutionary Computation Conference 2000年 口頭発表(招待・特別)
  • Designing Genetic Algorithms for Adaptive Routing Algorithms in the Internet  [招待講演]
    Masaharu Munetomo
    Workshop on Evolutionary telecommunications: Past, present, and future, at the 1999 Genetic and Evolutionary Computation Conference 1999年 口頭発表(招待・特別)

担当経験のある科目(授業)

  • 一般教育演習北海道大学
  • 知識系工学特論北海道大学
  • 情報処理II北海道大学
  • 情報処理I北海道大学
  • 情報科学北海道大学
  • 知能情報学特論室蘭工業大学
  • 情報数理科学特別講義大阪府立大学
  • 科学技術英語演習北海道大学
  • 情報工学実験第一北海道大学
  • 情報学II北海道大学
  • 計算システム設計学特論北海道大学
  • ソフトウェア方法論北海道大学
  • メディアコンテンツ工学北海道大学
  • ネットワークとクラウド北海道大学
  • 基礎数学北海道工業大学
  • 情報システム設計学特論北海道大学

所属学協会

  • 進化計算学会   米国電気電子学会   情報処理学会   IEEE   Information processing society of Japan   

共同研究・競争的資金等の研究課題

  • 日本学術振興会:科学研究費助成事業
    研究期間 : 2023年04月 -2028年03月 
    代表者 : 南 弘征, 棟朝 雅晴, 馬場 健一, 水田 正弘, 山岡 克式
  • 日本学術振興会:科学研究費助成事業
    研究期間 : 2021年09月 -2026年03月 
    代表者 : 中垣 俊之, 棟朝 雅晴, 田中 良巳, 國田 樹, 佐藤 勝彦
  • ジオラマ環境で覚醒する原生知能を定式化する細胞行動力学:アルゴリズム評価班
    日本学術振興会:科学研究費助成事業 学術変革領域研究(A)
    研究期間 : 2021年09月 -2026年03月 
    代表者 : 中垣 俊之, 佐藤 勝彦, 田中 良巳, 棟朝 雅晴, 國田 樹
  • 日本学術振興会:科学研究費助成事業 基盤研究(C)
    研究期間 : 2020年04月 -2023年03月 
    代表者 : 棟朝 雅晴
     
    令和3年度においては、大規模かつ困難な最適化問題の解決に必要となるアルゴリズムの開発を進め、スケーラブルなリンケージ同定手法の開発ならびに実問題への適用について研究を行った。具体的には、スケーラブルなリンケージ同定手法として、sLIEM (scalable Linkage Identification with Epistasis Measures)の開発ならびに、合成人口モデルに関わる最適化問題への適用を行った。進化計算において互いに関連のある遺伝子を同定するリンケージ同定手法は、個体長の2乗オーダーの計算量を必要とし、多項式オーダーではあるが大規模問題となった場合にその計算量が課題となる。本研究課題で開発したsLIEMは、重要な変数(遺伝子)に関する摂動を中心としてリンケージ同定の対象を絞り込むことで、その計算量を削減しつつ、実問題におけるリンケージ同定の精度を確保している。 スケーラブルなリンケージ同定手法の提供例として、村田らによる合成人口モデルに関わる最適化問題へ適用し、従来手法と比較した優位性を検証した。合成人口モデルは、公開されている自治体の人口分布に関する統計データから、住民それぞれの世帯構成を推定し合成することで、プライバシーを保護しつつ、社会シミュレーションに必要とされる基礎的な人口モデルを求める手法であり、従来手法においては擬似焼き鈍し法を用いた最適化手法が提案されていた。本研究で開発したスケーラブルなリンケージ同定を導入した並列進化計算を用いることで、生成される合成人口モデルの精度を向上(誤差を低減)することができた。また、スケーラブルなリンケージ同定に加え、さらにACO (Ant Colony Optimization)の大規模並列実装、実問題への応用についても検討に着手し、次年度にその成果を公表する計画である。
  • 最適資源選択技術に関する研究(インタークラウドを活用したアプリケーション中心型オーバーレイクラウド技術に関する研究:主たる共同研究者)
    JST:CREST
    研究期間 : 2015年10月 -2021年03月 
    代表者 : 棟朝 雅晴
  • 日本学術振興会:科学研究費助成事業 基盤研究(C)
    研究期間 : 2014年04月 -2017年03月 
    代表者 : 小林 泰三, 棟朝 雅晴, 實本 英之, 高見 利也, 南里 豪志, 森江 善之
     
    連成計算や大規模な数値計算ではファイルの移動やマージなどのI/Oが多く占められており大きなボトルネックになっている。この問題を解決するために、ファイルI/Oを介さずプロセス間同士が直接通信するスキームを研究開発した。具体的には(1)通信スキームの要素技術を洗い出し、C言語の stdio の要領で通信を可能にする NSTDIO を研究開発した。(2)次に、基盤センター間でジョブの連携を行うなどの多拠点間連携をユーザー権限のみで実現するフレームワークである EGCPOPS を研究開発した。(3)最後に、これらのフレームワークが稼働するために必要な不確定要素対応機構SRXの概念設計を行った。
  • 日本学術振興会:科学研究費助成事業 基盤研究(A)
    研究期間 : 2012年05月 -2016年03月 
    代表者 : 合田 憲人, 坂根 栄作, 棟朝 雅晴, 小林 泰三
     
    複数拠点のクラウドを連携させた基盤を構築し,学術コミュニティの研究教育活動に利用することが期待されている.しかし,複数拠点のクラウドにアプリケーションプログラムを適切に割り当てる負荷分散技術は未だ確立されていない.本研究では,複数拠点のクラウドを活用して高性能かつ高信頼な処理を可能とするための負荷分散技術に関する研究を行なった.具体的には,クラウド上でのアプリケーション性能を表すモデルを考案するとともに,アプリケーションの性能の特徴を収集して適切なクラウドを選択するためのシステムを開発した.
  • 日本学術振興会:科学研究費助成事業 基盤研究(C)
    研究期間 : 2010年04月 -2014年03月 
    代表者 : 棟朝 雅晴
     
    本研究においては、進化計算アルゴリズムの改良として混合分布モデルへの拡張を行ったBOA-MD、局所探索との融合を行ったBHCS、MINLP (Mixed-Integer Non-Linear Programming)のためのARGAおよびBRGAを開発するとともに、進化計算の大規模並列化としてメニーコアアーキテクチャにおける大規模並列実装を行うとともに、クラウド環境への展開も図った。 現実の問題に対する適用例として、MINLP問題としてのクラウド資源最適化問題や、薬剤の構造を自動的に最適化することを目指したde novo Ligand Docking問題等へ適用し、その有効性を検証した。
  • アカデミックインタークラウドの実現に向けた連携基盤技術に関する研究
    国立情報学研究所:国立情報学研究所一般公募型共同研究
    研究期間 : 2014年 -2014年 
    代表者 : 棟朝 雅晴
  • 日本学術振興会:科学研究費助成事業 特定領域研究
    研究期間 : 2006年 -2010年 
    代表者 : 安達 淳, 田中 克己, 西田 豊明, 國吉 康夫, 須藤 修, 黒橋 禎夫, 原 隆弘, 松岡 聡, 田浦 健次朗, 建部 修見, 棟朝 雅晴, 廣津 登志夫, 松原 仁, 下條 真司, 千葉 滋, 湯淺 太一, 松山 隆司, 近山 隆, 近堂 徹, 河野 健二, 岡本 正宏, 合田 憲人, 鎌田 十三郎, 喜連川 優, 山名 早人, 中村 豊, 小林 広明, 中島 浩, 喜連川 優, 下條 真司, 千葉 滋
     
    本特定領域に参加する計画・公募研究班で共用するための研究基盤を構築し、研究活動の支援を行った。これにより、限られた経費の中で研究資源の共用を図り研究連携を深める効果を発揮した。具体的には開放型検索エンジンTSUBAKIによる大規模コーパスの提供、広域分散コンピューティングテストベッドInTrigger、実世界インタラクション計測分析環境IMADE、そしてセンサーネットワーク予防医療の実験環境を構築した。
  • 日本学術振興会:科学研究費助成事業 若手研究(B)
    研究期間 : 2006年 -2008年 
    代表者 : 棟朝 雅晴
     
    本研究においては、遺伝子解析による高度な進化計算アルゴリズムを大規模並列化するとともに、グリッドコンピューティングシステムなど最新の大規模並列計算環境における実装を行った。さらには、最適化問題を解きたい設計者の有するシミュレーションプログラムとの連携を容易に行うためのフレームワークを提案することで、大規模かつ複雑な現実の設計問題、最適化問題を解決するための基盤となるシステムのプロトタイプを開発した。
  • 日本学術振興会:科学研究費助成事業 萌芽研究
    研究期間 : 2004年 -2005年 
    代表者 : 赤間 清, 棟朝 雅晴
     
    メタ計算は、仕様から正当なプログラムを生成するための新しい方法である。 メタ計算では、計算状態の束をメタ節集合で表現し、メタルールで変換を次々に行うことによって新しいメタ節を得る。最初と最後のメタ節集合のペアから正当なルールを得ることができ、そのようなルールを集めることによって、プログラムを得ることができる。 得られたプログラムの(部分)正当性は、個々のメタルールの正当性から保証できる。 正しいメタルールを仕様から作る方法もすでに与えられている。 このルール生成のパラメータは、最初のメタ節集合とルール適用の2つである。ルール適用は、メタ節集合のどの位置にどのメタルールを適用するか、それを何回繰り返すかである。本研究では、これらのパラメータを遺伝子にコーディングして、進化的探索によって、よりよいルールを低コストで発見する方法を提案した。その際、ルールの評価として、分岐数が少なく、節のサイズが小さいものを優先する指標を用いた。 ポイントとなるのは遺伝子へのコーディングである。ルール適用の可能性はそのときのメタ節集合によって大きく変わるので、あらかじめ遺伝子の空間を固定するのは得策ではない。そこで、メタ節集合とメタルールが与えられたとき、ルール適用の可能性の集合を高速に計算する手法や、その中のルール適用の1つの可能性をメタ節集合に適用して、次のメタ節集合を求める手法を考案し、それらをET言語に組み込み述語として導入した。これにより、メタ計算を基礎とした進化的探索のアルゴリズムの実現が容易になり、メタ計算の探索に基づくプログラム生成を効率的に行うことが可能になった。
  • 日本学術振興会:科学研究費助成事業 若手研究(B)
    研究期間 : 2003年 -2005年 
    代表者 : 棟朝 雅晴
     
    本研究においては、これまでに提案されたリンケージ同定に基づく遺伝的アルゴリズムをさらに発展させ、より一般的な枠組みとして、遺伝子解析に基づく遺伝的アルゴリズムを開発することを目的とし、さらにそのシステム設計問題への応用をはかっている。バイオインフォマティクスの分野では、遺伝子解析に関する手法が数多く提案されているが、それらを参考にリンケージの同定、ビルディングブロックの検出、交叉手法の改良などを行い、より高性能で高い信頼性を有する遺伝的アルゴリズムを開発する。 本年度においては、分布推定手法の改良を図るとともに、効率的な並列化手法を開発することで、大規模な問題への対応を図った。具体的には、割り当て関数による重み付けを行うことで精度を向上させ分布推定に要する計算コストを削減するための手法を開発するとともに、ベイジアンネットワークに基づく確率モデル構築を行う分布推定アルゴリズムにおいて、ネットワーク構築の効果的な並列化手法を開発した。 さらには、リンケージ同定と分布推定アルゴリズムの双方の利点を組み合わせたアルゴリズムD^5の開発を行い、問題規模の増大に対するスケーラビリティに優れた手法を開発した。さらに、D^5の実数値問題への適用についても議論するとともに、その性能について評価を行った。 提案手法の適用例として、特に、蛋白質の構造エネルギー最小化問題へ、並列化した分布推定による探索手法を適用することで、本研究で開発した手法の有効性を検証している。
  • 日本学術振興会:科学研究費助成事業 若手研究(B)
    研究期間 : 2001年 -2002年 
    代表者 : 棟朝 雅晴
     
    本研究においては、線型・非線型および単調・非単調性を調べることによって関連する遺伝子座のまとまりであるリンケージ集合を同定し、効果的な交叉を実現する手法に関してその理論的基礎を確立するとともに、理論に基づいた遺伝的アルゴリズムの設計、特に交叉手法の改良を行うことで、大規模な最適化問題におけるアルゴリズムの性能を評価した。リンケージ集合の構造として、これまでの研究では比較的単純な線形の構造が仮定されていたが、本研究では階層構造を有するリンケージの同定を行う手法である、hLIEM(hierarchical Linkage Identification with Epistasis Measure)およびhLIEM^2(hierarchical Linkage Identification with Epistasis Measure considering Monotonicity)を開発した。これら手法においては、小さなリンケージ集合をまとめてより大きなリンケージ集合を生成するという過程を繰り返すことで、現実問題の多くが有すると考えられる問題の階層構造を同定することが可能となり、交叉など遺伝的操作をさらに効率的に適用することが可能となった。 本研究で開発した階層型のリンケージ同定アルゴリズムの有効性を、階層型のトラップ関数に代表される各種のテスト関数において確認したが、さらに現実の問題として都市圏ネットワーク設計問題へと適用し、その有効性を確かめた。大規模なネットワークを設計する場合、ゆるやかな階層構造を有するようなネットワークとして設計を行うことが考えられるが、本研究で提案するアルゴリズムにより、人間の設計者が介在することなく、計算機により自動的に適切な階層構造を有するネットワークを構成することができ、従来の手法に比べて、より低コストで高性能なネットワークを設計することができた。
  • 日本学術振興会:科学研究費助成事業 基盤研究(B)
    研究期間 : 2000年 -2002年 
    代表者 : 赤間 清, 棟朝 雅晴, 水田 正弘
     
    1.メタ計算の一般理論の構築 分離記述と呼ばれる新しい表現システムのクラスを基礎として、プログラム生成の一般的な枠組みを構築した。また、プログラム変換とルール生成の本質的な差異が明らかになった。さらに、プログラム変換によるプログラム生成は、本研究のプログラム生成の真のサブクラスであり、ルール生成部分を最小限にしたものとみなすことができることを示した。 2.一階論理表現を処理できるシステムへの拡張 一階論理表現を含むメタ記述の概念を定義し、その変換により,ルールそしてプログラムをつくり出す実験を行ない、いくつかの例題で成功を収めた。たとえば、言語を一階述語表現で記述し、それを認識する有限オートマトンを自動生成することに成功した。 3.メタ計算の拡張 より広いクラスのルールを生成できるように、メタ表現を拡張した。具体的には、変数に対する制約条件を扱えるように表現の拡張を施し、それに対するメタ計算の理論を開発した。これによって、条件部を持つルールの生成が可能となった。また、それに対する理論的な基礎を検討した。たとえば最大値を求めるプログラムでは、ルールに変数の大小比較の条件が必要になる。これはメタ変数に不等式条件をつけ、それを用いて正しくメタ計算することで達成できる。 4.作成したプログラム自動生成システムの評価 構文解析プログラムを自動生成する問題に適用した。その結果、著しい高速化が達成され、実用的に意味のあるプログラムが得られることが判明した。ただし、得られたプログラムは、さらに高速化できる可能性がある。それは実行部の最大化や、決定性プログラムへの変換である。それについても手動で検討したが、完全な自動化については今後の課題として残された。
  • 日本学術振興会:科学研究費助成事業 奨励研究(A)
    研究期間 : 1999年 -2000年 
    代表者 : 棟朝 雅晴
     
    本研究では、進化的計算手法、特に遺伝的アルゴリズムを用いた経路制御アルゴリズムに関して、大規模ネットワーク上での性能評価を行い、アルゴリズムの改良を行った。改良点としては、適応度を評価するために必要なネットワーク状態の観測法について、従来は評価パケットが到着するまでの時間を用いていたのに対し、改良したアルゴリズムでは各リンクの負荷状態を離散化した情報を収集することでより高速かつ効率的にネットワークの負荷状態を観測することができた。さらには代替経路を生成するために使用される遺伝的操作に関してもリンクの負荷状態を考慮した交叉および突然変異の手法を開発することでアルゴリズムの改良を行った。提案したアルゴリズムの評価を行うため、イベントシミュレーション手法に基づくネットワークシミュレータを開発し、大規模シミュレーションにより改良手法の有効性を確認した。 本研究では、さらに、ネットワーク資源管理アルゴリズムとして分散型帯域幅割当アルゴリズムを開発した。特定の通信リンクや小規模ネットワークを対象とした場合、通信帯域割当などの資源管理は集中管理方式により比較的容易に行うことができるが、大規模ネットワーク上においては、必然的に不確実な情報を基にした分散管理を行わざるを得なくなり、単純な最適化問題としてとらえることはできない。このような状況において、遺伝的アルゴリズムを用いた分散型帯域幅割当アルゴリズムを構築し、その有効性をシミュレータによるシミュレーション実験と通して検証した。
  • 日本学術振興会:科学研究費助成事業 奨励研究(A)
    研究期間 : 1997年 -1998年 
    代表者 : 棟朝 雅晴
     
    本研究では、複雑系、人工生命に関連して近年注目を集めている遺伝的アルゴリズムをインターネットにおける経路制御アルゴリズムへ応用することで、ネットワークの負荷変化に動的するアルゴリズムを構築する。 現在一般に使用されているルーティングアルゴリズムでは、ネットワークの負荷状態や通信リンクの性能などを考慮せず、単純に通過したゲートウェイの数で表されるホップカウント距離を用いていた。そこで、ネットワークの負荷状態を考慮した適応型のルーティングアルゴリズムを少ない通信負荷で実現するため、遺伝的アルゴリズムにより必要な代替経路群を動的に生成するアルゴリズムを構築した。 代替経路を効率的に生成するため、特別に設計された経路遺伝的操作(Path Genetic Operators)を提案した。提案するルーティングアルゴリズムにおいては、初期経路として、従来と同様のホップカウント距離に基づいた最短経路を使用し、ある一定回数以上使用される経路に関して、代替経路を動的に生成し、各代替経路の通信遅延に応じてパケットを分配する。通信遅延の観測に関しては、ルーティングテーブルに存在する各経路に関して、定期的に通信遅延の観測パケットを送出するが、ルーティングテーブルには頻繁に使用される少数の代替経路のみ存在するため、少ない通信負荷で効果的な観測が行われる。 アルゴリズムの評価を行うため、離散事象シミュレータを構築し、その上でシミュレーション実験を行い、従来の代表的な手法であるRIP,SPFと比較した。その結果、今回提案した基本的なアルゴリズムにより、ネットワークの負荷が減少し、効果的に通信パケットが送出されていることが確かめられた。

産業財産権



Copyright © MEDIA FUSION Co.,Ltd. All rights reserved.