检索结果-内蒙古大学图书馆

Improving Combinatorial Optimization algorithms through Record Keeping in constructive Multistart Search

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS 2014年第9期29卷 864-879页

作者： King, Charles R. Tamir, Dan E. McKenney, Mark Texas State Univ Dept Comp Sci San Marcos TX 78666 USA So Illinois Univ Dept Comp Sci Edwardsville IL 62026 USA

constructive multistart search algorithms are commonly used to address combinatorial optimization problems;however, constructive multistart search algorithm performance is fundamentally affected by two factors: (i) The choice of construction algorithm utilized and (ii) the rate of state space search redundancy. Construction algorithms are typically specific to a particular combinatorial optimization problem;therefore, we first investigate construction algorithms for iterative hill climbing applied to the traveling salesman problem and experimentally determine the best performing algorithms. We then investigate the more general problem of utilizing record-keeping mechanisms to mitigate state space search redundancy. Our research shows that a good choice of construction algorithm paired with effective record keeping significantly improves the quality of traveling salesmen problem solutions in a constant number of state explorations. Particularly, we show that Bloom filters considerably improve time performance and solution quality for iterative hill climbing approaches to the traveling salesman problem. (C) 2014 Wiley Periodicals, Inc.

关键词： Improving Combinatorial Optimization algorithms constructive Multistart Search Optimization algorithms Climbing Combinatorial optimization algorithms constructivity SEARCHING algorithm constructive algorithm travelling salesman problems bloom state space

来源：评论

学校读者我要写书评

暂无评论

MEASURING THE ACCURACY OF ROM RECIPROCAL TABLES

引用

IEEE TRANSACTIONS ON COMPUTERS 1994年第8期43卷 932-940页

作者： DASSARMA, D MATULA, DW Dept. of Comput. Sci. & Eng. Southern Methodist Univ. Dallas TX USA

We prove that a convenient ROM reciprocal table construction algorithm generates tables that minimize the relative error. The worst case relative errors realized for such optimally computed k-bits-in, m-bits-out ROM reciprocal tables are then determined for all table sizes 3 less-than-or-equal-to k, m less-than-or-equal-to 12. We next prove the table construction algorithm always generates a k-bits-in, k-bits-out table with relative errors never any greater than 3/4 2-k for any k, and more generally with g guard bits that for (k + g)-bits-out the relative error is never any greater than 2-(k + 1) (1 + 1/2g+1). To provide for determining extreme case test data and to compute the precision of a reciprocal table without prior construction of the full ROM reciprocal table, we describe a procedure that requires generation and inspection of only a small portion of such a table to identify input values guranteed to include the worst case relative errors in the table.

关键词： observational data Reciprocal constructive algorithm relative errors input value Read Only Memory Device Component

来源：评论

学校读者我要写书评

暂无评论

On the optimal structure design of multilayer feedforward neural networks for pattern recognition

引用

INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE 2002年第4期16卷 375-398页

作者： Chen, DQ Burrell, P S Bank Univ Knowledge Based Syst Ctr Sch Comp Informat Syst & Math London SE1 0AA England

In this survey paper, the-state-of-the-art of the optimal structure design of Multilayer Feedforward Neural Network (MFNN) for pattern recognition is reviewed. Special emphasis is laid on the scale-limited MFNN and the internal representation and decision boundary-based design methodologies. A comprehensively comparative study of the main characteristics of each method is presented. Also, future research directions are outlined.

关键词： multilayer feedforward neural network multilayer perceptron internal representation pruning algorithm genetic algorithm constructive algorithm discriminant decision machine learning support vector machine

来源：评论

学校读者我要写书评

暂无评论

A New Approach to the Cloud-Based Heterogeneous MapReduce Placement Problem

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2016年第6期9卷 862-871页

作者： Xu, Xiaoyong Tang, Maolin Queensland Univ Technol Sch Elect Engn & Comp Sci Brisbane Qld 4000 Australia

Guaranteeing quality of service (QoS) with minimum computation cost is the most important objective of cloud-based MapReduce computations. Minimizing the total computation cost of cloud-based MapReduce computations is done through MapReduce placement optimization. MapReduce placement optimization approaches can be classified into two categories: homogeneous MapReduce placement optimization and heterogeneous MapReduce placement optimization. It is generally believed that heterogeneous MapReduce placement optimization is more effective than homogeneous MapReduce placement optimization in reducing the total running cost of cloud-based MapReduce computations. This paper proposes a new approach to the heterogeneous MapReduce placement optimization problem. In this new approach, the heterogeneous MapReduce placement optimization problem is transformed into a constrained combinatorial optimization problem and is solved by an innovative constructive algorithm. Experimental results show that the running cost of the cloud-based MapReduce computation platform using this new approach is 24: 3-44: 0 percent lower than that using the most popular homogeneous MapReduce placement approach, and 2: 0-36: 2 percent lower than that using the heterogeneous MapReduce placement approach not considering the spare resources from the existing MapReduce computations. The experimental results have also demonstrated the good scalability of this new approach.

关键词： MapReduce cloud-based MapReduce computation MapReduce placement combinatorial optimization constructive algorithm

来源：评论

学校读者我要写书评

暂无评论

Job shop scheduling with a combination of four buffering constraints

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2018年第9期56卷 3274-3293页

作者： Liu, Shi Qiang Kozan, Erhan Masoud, Mahmoud Zhang, Yu Chan, Felix T. S. Fuzhou Univ Sch Econ & Management Fuzhou Fujian Peoples R China Queensland Univ Technol Sch Math Sci Brisbane Qld Australia Univ S Florida Civil & Environm Engn Tampa FL USA Hong Kong Polytech Univ Dept Ind & Syst Engn Hong Kong Hong Kong Peoples R China

In this paper, a new scheduling problem is investigated in order to optimise a more generalised Job Shop Scheduling system with a Combination of four Buffering constraints (i.e. no-wait, no-buffer, limited-buffer and infinite-buffer) called CBJSS. In practice, the CBJSS is significant in modelling and analysing many real-world scheduling systems in chemical, food, manufacturing, railway, health care and aviation industries. Critical problem properties are thoroughly analysed in terms of the Gantt charts. Based on these properties, an applicable mixed integer programming model is formulated and an efficient heuristic algorithm is developed. Computational experiments show that the proposed heuristic algorithm is satisfactory for solving the CBJSS in real time.

关键词： job shop scheduling buffer management blocking no-wait mixed integer programming constructive algorithm best-insertion-heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Ant colony optimisation for task matching and scheduling

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 2006年第6期153卷 373-380页

作者： Chiang, C-W. Lee, Y-C. Lee, C-N. Chou, T-Y. Natl Kaohsiung First Univ Sci & Technol Dept Comp & Commun Engn Kaohsiung 811 Taiwan Natl Sun Yat Sen Univ Dept Comp Sci & Engn Kaohsiung 804 Taiwan

PC clusters have recently received considerable interest as cost-effective parallel platforms for CPU-intensive applications. A cluster of PCs generally comprises of a collection of heterogeneous process elements (PEs). To make effective use of a PC cluster, a parallel program, which is characterised by a node- and edge-weighted directed acyclic graph (DAG), can usually be decomposed into a set of precedence-constrained atomic tasks such that PEs are able to accommodate these tasks and minimise the overall program-completion time. Consequently, techniques for task matching and scheduling become extremely important for effectively harnessing the computing power of the target cluster-based system. This work presents a constructive algorithm based on ant colony optimisation (ACO). The proposed algorithm, namely ACO-TMS, adopts a new state transition rule that reduces the time required when finding the satisfactory scheduling results. The proposed algorithm also integrates a local search procedure that proposed to help improve the scheduling results. The performance of this algorithm is demonstrated by comparing it against other existing algorithms, such as the genetic -algorithm-based scheduling method and the dynamic priority scheduling (DPS) heuristic, in terms of overall schedule length of randomly generated DAGs. Experimental results indicate that the proposed algorithm outperforms the genetic algorithm and the DPS heuristic algorithm for high communication to computation and heterogeneous computing environment.

关键词： constructive algorithm task scheduling optimisation PC clusters Combinatorial mathematics heterogeneous process element Optimisation techniques task matching processor scheduling ant colony optimisation search problems Distributed systems software parallel program state transition rule directed acyclic graph ACO-TMS CPU-intensive applications local search procedure directed graphs

来源：评论

学校读者我要写书评

暂无评论

ERANN: An algorithm to Extract Symbolic Rules from Trained Artificial Neural Networks

引用

IETE JOURNAL OF RESEARCH 2012年第2期58卷 138-154页

作者： Kamruzzaman, S. M. Hamid, Md. Abdul Sarkar, A. M. Jehad Hankuk Univ Foreign Studies Dept Elect Engn Yongin 449791 Kyonggi Do South Korea

This paper presents an algorithm to extract symbolic rules from trained artificial neural networks (ANNs), called ERANN. In many applications, it is desirable to extract knowledge from ANNs for the users to gain a better understanding of how the networks solve the problems. Although ANN usually achieves high classification accuracy, the obtained results sometimes may be incomprehensible, because the knowledge embedded within them is distributed over the activation functions and the connection weights. This problem can be solved by extracting rules from trained ANNs. To do so, a rule extraction algorithm has been proposed in this paper to extract symbolic rules from trained ANNs. A standard three-layer feedforward ANN with four-phase training is the basis of the proposed algorithm. Extensive experimental studies on a set of benchmark classification problems, including breast cancer, iris, diabetes, wine, season, golfplaying, and lenses classification, demonstrates the applicability of the proposed method. Extracted rules are comparable with other methods in terms of number of rules, average number of conditions for a rule, and the rules accuracy. The proposed method achieved accuracy values 96.28, 98.67, 76.56, 91.01, 100, 100, and 100 for the above problems, respectively. It has been seen that these results are one of the best results comparing with results obtained from related previous studies.

关键词： Backpropagation Clustering algorithm constructive algorithm Continuous activation function Pruning algorithm Rule extraction algorithm Symbolic rules

来源：评论

学校读者我要写书评

暂无评论

A route set construction algorithm for the transit network design problem

引用

COMPUTERS & OPERATIONS RESEARCH 2009年第8期36卷 2440-2449页

作者： Mauttone, Antonio Urquhart, Maria E. Univ Republica Dept Operat Res Montevideo Uruguay

The transit network design problem (TNDP) aims to determine a set of bus routes for a public transportation system, which must be convenient from the viewpoints of both users (people who use public transportation) and operators (companies who own the resources to give the service). This article presents a constructive algorithm for the TNDP. It is specially designed to produce a set of routes that fulfils demand covering constraints, while taking into account the interests of both users and operators. Its general structure is inspired in the Route Generation algorithm (RGA) of Baaj and Mahmassani, where its original expansion of routes by inserting individual vertices is replaced by a strategy of insertion of pairs of vertices. The algorithm proposed, called Pair Insertion algorithm (PIA) can be used to generate initial solutions for a local improvement or evolutionary algorithm, as well as to complete an unfeasible solution with respect to demand covering constraints. Numerical results comparing PIA with RGA over a real test case show that both algorithms produce solutions with similar quality from the users viewpoint (in terms of in-vehicle travel time), while the former produces better solutions from the operators viewpoint (in terms of number of routes and total route duration) and requires a higher execution time. Since the TNDP arises in a context of strategic planning, a solution that reduces the operation cost of the system is highly desirable, even though it takes more time to be computed. The experimental study of the proposed algorithm also shows its ability to produce diverse solutions in both decision and objective spaces;this is a useful property when looking at the use of PIA as a subroutine in the context of another algorithm such as metaheuristics, in particular for a multi-objective problem like TNDP. (c) 2008 Elsevier Ltd. All rights reserved.

关键词： Transit network design problem constructive algorithm Heuristic Demand covering constraints

来源：评论

学校读者我要写书评

暂无评论

Construction of Dual-CISTs on an Infinite Class of Networks

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第8期33卷 1902-1910页

作者： Qin, Xiao-Wen Hao, Rong-Xia Wu, Jie Beijing Jiaotong Univ Dept Math Beijing 100044 Peoples R China Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA

The main method to achieve fault-tolerant network systems is by exploiting and effectively utilizing the edge-disjoint and/or inner-vertex-disjoint paths between pairs of source and destination vertices. Completely independent spanning trees (CISTs for short) are powerful tools for reliable broadcasting/unicasting and secure message distribution. Particularly, it has been shown that two CISTs have an application on configuring a protection routing in IP networks, such as mobile ad hoc networks and relatively large (static) network topologies with scalability in [IEEE/ACM Trans. Netw., 27 (2019) 1112-1123]. Many results focus on CISTs in specific networks in the literature, however, few results are given on an infinite class of networks having common properties. In this article, we prove the existence of dual-CISTs in an infinite number of networks satisfying some Hamilton sufficient conditions. A unique algorithm to construct a CIST-partition is proposed, which can be applied to not only many kinds of networks, but our algorithm can also be implemented very easily in parallel or distributed systems satisfying the conditions. In addition, we make a comparative analysis between the proposed conditions and several known results on an infinite number of networks, the advantage of our result is significant. In particular, the bound in our conditions is sharp. The results will provide a powerful framework for the design of fault-tolerant network topologies and routing protocols for future networks.

关键词： Fault tolerant systems Fault tolerance Hypercubes Tools Routing Network topology Broadcasting Completely independent spanning trees a protection routing CIST-partition Hamilton bipartition sufficient condition constructive algorithm

来源：评论

学校读者我要写书评

暂无评论

Bounds for the connected domination number of maximal outerplanar graphs

引用

DISCRETE APPLIED MATHEMATICS 2022年 320卷 235-244页

作者： Chen, Shao-Liang Hao, Rong-Xia Qin, Xiao-Wen Beijing Jiaotong Univ Sch Math & Stat Beijing 100044 Peoples R China

A dominating set of a graph G is a set S subset of V(G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number, denoted by gamma(c)(G). Zhuang showed that gamma(c)(G) of a maximal outerplanar graph G is bounded by min{left perpendicular n+k/2 right perpendicular - 2, left perpendicular 2(n-k)/3 right perpendicular} (Zhuang, 2020), where k is the number of 2-degree vertices in G. In this paper, we give an algorithm for finding a connected dominating set of maximal outerplanar graphs and get an upper bound gamma(c)(G) <= left perpendicular n-k+x/2 right perpendicular, where x is a counter in the algorithm and x <= k - 2. As a corollary, the result that gamma(c)(G) <= left perpendicular n-2/2 right perpendicular for a maximal outerplanar G is gotten directly. This results is better than the above known bound for 3 < k < n+6/4. In addition, we complement some analysis with simulations to evaluate the advantages of our results. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Maximal outerplanar graph Connected dominating set Connected domination number constructive algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：