共查询到20条相似文献,搜索用时 734 毫秒
1.
New Meta-Heuristic for Combinatorial Optimization Problems: Intersection Based Scaling 总被引:1,自引:0,他引:1
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
PengZou ZhiZhou Ying-YuWan Guo-LiangChen JunGu 《计算机科学技术学报》2004,19(6):0-0
Combinatorial optimization problems are found in many application fields such as computer science,engineering and economy. In this paper, a new efficient meta-heuristic, Intersection-Based Scaling (IBS for abbreviation), is proposed and it can be applied to the combinatorial optimization problems. The main idea of IBS is to scale the size of the instance based on the intersection of some local optima, and to simplify the search space by extracting the intersection from the instance, which makes the search more efficient. The combination of IBS with some local search heuristics of different combinatorial optimization problems such as Traveling Salesman Problem (TSP) and Graph Partitioning Problem (GPP) is studied, and comparisons are made with some of the best heuristic algorithms and meta-heuristic algorithms. It is found that it has significantly improved the performance of existing local search heuristics and significantly outperforms the known best algorithms. 相似文献
2.
Optimal bandwidth utilization of all-optical ring with a converter of degree 4 总被引:3,自引:0,他引:3
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
In many models of all-optical routing,a set of communication paths in a network is given,and a wavelength is to be assigned to each path so that paths sharing an edge receive different wavelengths .The goal is to assign as few wavelengths as possible,in order to use the optical bandwidth efficiently.If a node of a network contains a wavelength converter,any path that passes through this node may change its wavelength .Having converters at some of the nodes can reduce the mumber of wavelengths required for routing,This paper presents a wavelength converter with degree 4and gives a routing algorithm which shows that any routing with load L can be realized with L wavelengths when a node of an all-optical ring hosts such a wavelength converter.It is also proved that 4 is the minimum degree of the converter to reach the full utilization of the available wavelengths if only one mode of an all-optical ring hosts a converter. 相似文献
3.
1IntroductionMulticastcommunication,whichreferstothedeliveryofamessagefromasinglesourcenodetoanumberofdestinationnodes,isfrequentlyusedindistributed-memoryparallelcomputersystemsandnetworks[1].Efficientimplementationofmulticastcommunicationiscriticaltotheperformanceofmessage-basedscalableparallelcomputersandswitch-basedhighspeednetworks.Switch-basednetworksorindirectnetworks,basedonsomevariationsofmultistageiDterconnectionnetworks(MINs),haveemergedasapromisingnetworkajrchitectureforconstruct… 相似文献
4.
Ant colony optimization (ACO for short) is a meta-heuristics for hard combinatorial optimization problems. It is a population-based
approach that uses exploitation of positive feedback as well as greedy search. In this paper, genetic algorithm's (GA for
short) ideas are introduced into ACO to present a new binary-coding based ant colony optimization. Compared with the typical
ACO, the algorithm is intended to replace the problem's parameter-space with coding-space, which links ACO with GA so that
the fruits of GA can be applied to ACO directly. Furthermore, it can not only solve general combinatorial optimization problems,
but also other problems such as function optimization. Based on the algorithm, it is proved that if the pheromone remainder
factor ρ is under the condition of ρ≥1, the algorithm can promise to converge at the optimal, whereas if 0<ρ<1, it does not.
This work is supported by the Science Foundation of Shanghai Municipal Commission of Science and Technology under Grant No.00JC14052.
Tian-Ming Bu received the M.S. degree in computer software and theory from Shanghai University, China, in 2003. And now he is a Ph.D.
candidate of Fudan University in the same area of theory computer science. His research interests include algorithms, especially,
heuristic algorithms and heuristic algorithms and parallel algorithms, quantum computing and computational complexity.
Song-Nian Yu received the B.S. degree in mathematics from Xi'an University of Science and Technology, Xi'an, China, in 1981, the Ph.D.
degree under Prof. L. Lovasz's guidance and from Lorand University, Budapest, Hungary, in 1990. Dr. Yu is a professor in the
School of Computer Engineering and Science at Shanghai University. He was a visiting professor as a faculty member in Department
of Computer Science at Nelson College of Engineering, West Virginia University, from 1998 to 1999. His current research interests
include parallel algorithms' design and analyses, graph theory, combinatorial optimization, wavelet analyses, and grid computing.
Hui-Wei Guan received the B.S. degree in electronic engineering from Shanghai University, China, in 1982, the M.S. degree in computer
engineering from China Textile University, China, in 1989, and the Ph.D. degree in computer science and engineering from Shanghai
Jiaotong University, China, in 1993. He is an associate professor in the Department of Computer Science at North Shore Community
College, USA. He is a member of IEEE. His current research interests are parallel and distributed computing, high performance
computing, distributed database, massively parallel processing system, and intelligent control. 相似文献
5.
Chunming Hu Yanmin Zhu Jinpeng Huai Yunhao Liu Lionel M. Ni 《Knowledge and Information Systems》2007,12(1):55-75
Information service plays a key role in grid system, handles resource discovery and management process. Employing existing
information service architectures suffers from poor scalability, long search response time, and large traffic overhead. In
this paper, we propose a service club mechanism, called S-Club, for efficient service discovery. In S-Club, an overlay based
on existing Grid Information Service (GIS) mesh network of CROWN is built, so that GISs are organized as service clubs. Each
club serves for a certain type of service while each GIS may join one or more clubs. S-Club is adopted in our CROWN Grid and
the performance of S-Club is evaluated by comprehensive simulations. The results show that S-Club scheme significantly improves
search performance and outperforms existing approaches.
Chunming Hu is a research staff in the Institute of Advanced Computing Technology at the School of Computer Science and Engineering,
Beihang University, Beijing, China. He received his B.E. and M.E. in Department of Computer Science and Engineering in Beihang
University. He received the Ph.D. degree in School of Computer Science and Engineering of Beihang University, Beijing, China,
2005. His research interests include peer-to-peer and grid computing; distributed systems and software architectures.
Yanmin Zhu is a Ph.D. candidate in the Department of Computer Science, Hong Kong University of Science and Technology. He received his
B.S. degree in computer science from Xi’an Jiaotong University, Xi’an, China, in 2002. His research interests include grid
computing, peer-to-peer networking, pervasive computing and sensor networks. He is a member of the IEEE and the IEEE Computer
Society.
Jinpeng Huai is a Professor and Vice President of Beihang University. He serves on the Steering Committee for Advanced Computing Technology
Subject, the National High-Tech Program (863) as Chief Scientist. He is a member of the Consulting Committee of the Central Government’s Information Office, and Chairman of the Expert Committee in both the National e-Government Engineering Taskforce and the National e-Government Standard office. Dr. Huai and his colleagues are leading the key projects in e-Science of the National Science Foundation of China (NSFC)
and Sino-UK. He has authored over 100 papers. His research interests include middleware, peer-to-peer (P2P), grid computing,
trustworthiness and security.
Yunhao Liu received his B.S. degree in Automation Department from Tsinghua University, China, in 1995, and an M.A. degree in Beijing
Foreign Studies University, China, in 1997, and an M.S. and a Ph.D. degree in computer science and engineering at Michigan
State University in 2003 and 2004, respectively. He is now an assistant professor in the Department of Computer Science and
Engineering at Hong Kong University of Science and Technology. His research interests include peer-to-peer computing, pervasive
computing, distributed systems, network security, grid computing, and high-speed networking. He is a senior member of the
IEEE Computer Society.
Lionel M. Ni is chair professor and head of the Computer Science and Engineering Department at Hong Kong University of Science and Technology.
Lionel M. Ni received the Ph.D. degree in electrical and computer engineering from Purdue University, West Lafayette, Indiana,
in 1980. He was a professor of computer science and engineering at Michigan State University from 1981 to 2003, where he received
the Distinguished Faculty Award in 1994. His research interests include parallel architectures, distributed systems, high-speed
networks, and pervasive computing. A fellow of the IEEE and the IEEE Computer Society, he has chaired many professional conferences
and has received a number of awards for authoring outstanding papers. 相似文献
6.
In this paper,ARM iner,a data mining tool based on association rules,is introduced.Beginning with the system architecture,the characteristics and functions are discussed in details,including data transfer,concept hierarchy generalization,mining rules with negative items and the re-development of the system.An example of the tool‘s application is also shown.Finally,Some issues for future research are presented. 相似文献
7.
This paper is devtoed to a new algebraic modelling approach to distributed problem-solving in multi-agent systems(MAS),which is featured by a unified framework for describing and treating social behaviors,social dynamics and social intelligence.A coneptual architecture of algebraic modelling is presented.The algebraic modelling of typical social be-haviors,social situation and social dynamics is discussed in the context of distributed problem-solving in MAS .The comparison and simulation on distributed task allocations and resource assignments in MAS show more advantages of the algebraic approach than other conventional methods. 相似文献
8.
Bounded Slice-line Grid (BSG) is an elegant representation of block placement, because it is very intuitionistic and has the advantage of handling various placement constraints. However, BSG has attracted little attention because its evaluation is very time-consuming. This paper proposes a simple algorithm independent of the BSG size to evaluate the BSG representation in O(nloglogn) time, where n is the number of blocks. In the algorithm, the BSG-rooms are assigned with integral coordinates firstly, and then a linear sorting algorithm is applied on the BSG-rooms where blocks are assigned to compute two block sequences, from which the block placement can be obtained in O(n log logn) time. As a consequence, the evaluation of the BSG is completed in O(nloglogn) time, where n is the number of blocks. The proposed algorithm is much faster than the previous graph-based O(n^2) algorithm. The experimental results demonstrate the efficiency of the algorithm. 相似文献
9.
When querying on a large-scale knowledge base,a major technique of improving performance is to preload knowledge to minimize the number of roundtrips to the knowledge base.In this paper,an ontology-based semantic cache is proposed for an agent and ontology-oriented knowledge base (AOKB).In AOKB,an ontology is the collection of relationships between a group of knowledge units (agents and/or other sub-ontologies).When loading some agent A,its relationships with other knowledge units are examined,and those who have a tight semantic tie with A will be preloaded at the same time,including agents and sub-ontologies in the same ontology where A is.The proloaded agents and ontologies are saved at a semantic cache located in the memory.Test results show that up to 50% reduction in running time is achieved. 相似文献
10.
In modern VLSI technology, hundreds of thousands of arithmetic units fit on a 1cm^2 chip. The challenge is supplying them with instructions and data. Stream architecture is able to solve the problem well. However, the applications suited for typical stream architecture are limited. This paper presents the definition of regular stream and irregular stream, and then describes MASA (Multiple-morphs Adaptive Stream Architecture) prototype system which supports different execution models according to applications' stream characteristics. This paper first discusses MASA architecture and stream model, and then explores the features and advantages of MASA through mapping stream applications to hardware. Finally MASA is evaluated by ten benchmarks. The result is encouraging. 相似文献
11.
The faster higher-order cellular automaton for hyper-parallel undistorted data compression
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
This paper defines second-order and third-order permutation global functions and presents the corresponding higher-order cellular automaton approach to the hyper-parallel undistorted data compression.The genetic algorithm is successfully devoted to finding out all the correct local compression rules for the higher-order cellualr automaton.The correctness of the higher-order compression rules,the time complexity,and the systolic hardware implementation issue are discussed.In comparison with the first-order automation method reported,the proposed higher-order approach has much faster compression speed with almost the same degree of cellular structure complexity for hardware implementation. 相似文献
12.
BCL—3:Aigh Performance Basic Communication Protocol for Commodity Superserver DAWNING—3000
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
This paper introduces the design and implemetation of BCL-3,a high performance low-level communication software running on a cluster of SMPs(CLUMPS) called DAWNING-3000,BCL-3 provides flexible and sufficient functionality to fulfill the communication requirements of fundamental system software developed for DAWNING-3000 while guaranteeing security,scalability,and reliability,Important features of BCL-3 are presented in the paper,including special support for SMP and heterogeneous network environment,semiuser-level communication,reliable and ordered data transfer and scalable flow control,The performance evaluation of BCL-3 over Myrinet is also given. 相似文献
13.
A General Probability Formula of the Number of Location Areas' Boundaries Crossed by a Mobile Between Two Successive Call Arrivals 总被引:1,自引:0,他引:1
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Yi-HuaZhu Ding-HuaShi YongXiong JiGao He-ZhiLuo 《计算机科学技术学报》2004,19(2):177-182
Mobility management is a challenging topic in mobile computing environment. Studying the situation of mobiles crossing the boundaries of location areas is significant for evaluating the costs and performances of various location management strategies. Hitherto, several formulae were derived to describe the probability of the number of location areas‘ boundaries crossed by a mobile. Some of them were widely used in analyzing the costs and performances of mobility management strategies. Utilizing the density evolution method of vector Markov processes, we propose a general probability formula of the number of location areas‘ boundaries crossed by a mobile between two successive calls. Fortunately, several widely-used formulae are special cases of the proposed formula. 相似文献
14.
HarkMan—A Vocabulary-Independent Keyword Spotter for Spontaneons Chinese Speech 总被引:2,自引:0,他引:2
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
In this paper,a noverl technique adopted in HarkMan is introduced.HarkMan is a keywore-spotter designed to automatically spot the given words of a vocabulary-independent task in unconstrained Chinese telephone speech.The speaking manner and the number of keywords are not limited.This paper focuses on the novel technique which addresses acoustic modeling,keyword spotting network,search strategies,robustness,and rejection.The underlying technologies used in HarkMan given in this paper are useful not only for keyword spotting but also for continuous speech recognition.The system has achieved a figure-of-merit value over 90%. 相似文献
15.
Given an m×n mesh-connected VLSI array with some faulty elements, the reconfiguration problem is to find a maximum-sized fault-free sub-array under the row and column rerouting scheme. This problem has already been shown to be NP-complete. In this paper, new techniques are proposed, based on heuristic strategy, to minimize the number of switches required for the power efficient sub-array. Our algorithm shows that notable improvements in the reduction of the number of long interconnects could be realized in linear time and without sacrificing on the size of the sub-array. Simulations based on several random and clustered fault scenarios clearly reveal the superiority of the proposed techniques. 相似文献
16.
In today‘s Internet computing world,illegal activities by crackers pose a serious threat to computer security.It is well known that computer viruses,Trojan horses and other intrusive programs may cause sever and often catastrophic consequences. This paper proposes a novel secure computer architecture based on security-code.Every instruction/data word is added with a security-code denoting its security level.External programs and data are automatically addoed with security-code by hadware when entering a computer system.Instruction with lower security-code cannot run or process instruction/data with higher security level.Security-code cannot be modified by normal instruction.With minor hardware overhead,then new architecture can effectively protect the main computer system from destruction or theft by intrusive programs such as computer viruses.For most PC systems it includes an increase of word-length by 1 bit on register,the memory and the hard disk. 相似文献
17.
Processors arrays with reconfigurable bus systems (abbreviated to PARBS) have been received a lot of attention in the last
decade, and many undirected graph algorithms with constant time complexity have been proposed on PARBS. However, for a directed
graph, it will be proved that connecting PARBS in the way proposed for undirected graphs generates paths which do not exist
in the directed graph. This result may lead to incorrect solution for directed graph problems. Therefore, in this paper, a
model named D-PARBS (Directional PARBS) is proposed for eliminating the non-existent paths. This model can be used to correctly
identifying redundant arcs on directed graphs in constant time. Furthermore, by modifying the D-PARBS architecture, constant
time algorithms with O(n
3) processors are developed to solve topological sort, transitive closure, cyclic graph checking, and strongly connected component
problems on directed graphs.
Chi-Jung Kuo: He is currently an operation officer of the Information Processing Department in the Taipei Branch of Bangkok Bank. His
research interests include parallel processing and graph theory. He received his B.S. and M.S. degree in Information Management
from National Taiwan University of Science and Technology in 1993 and 1995, respectively. He was a teacher in the Chin Min
Junior College from 1995 to 1996.
Chiun-Chieh Hsu, Ph.D.: He is currently a full professor of Information Management Department at National Taiwan University of Science and Technology.
His current research interests include fault-tolerant computing, parallel and distributed processing, networks, and graph
theory. He received his B.E., M.E., and Ph.D. degrees all in Electrical Engineering from National Taiwan University in 1983,
1987, and 1990, respectively. He worked as a software and firmware design engineer of Research and Development in Acer Computer
Company from 1983 to 1985.
Wei-Chen Fang: He received the BS degree in MIS from Tamkang University and the MS degree in Information Management from National Taiwan
University of Science and Technology. Currently, he is a Ph.d student and works as an assistant researcher with the Advanced
Technology research group for Chunghwa Telecommunication Laboratory. His research interests include multi-processor architecture,
fault-tolerant computing, and parallel and distributed processing. 相似文献
18.
Summary Byzantine Agreement is important both in the theory and practice of distributed computing. However, protocols to reach Byzantine Agreement are usually expensive both in the time required as well as in the number of messages exchanged. In this paper, we present a self-adjusting approach to the problem. The Mostly Byzantine Agreement is proposed as a more restrictive agreement problem that requires that in the consecutive attempts to reach agreement, the number of disagreements (i.e., failures to reach Byzantine Agreement) is finite. Fort faulty processes, we give an algorithm that has at mostt disagreements for 4t or more processes. Another algorithm is given forn3t+1 processes with the number of disagreements belowt
2/2. Both algorithms useO(n
3) message bits for binary value agreement.
Yi Zhao is currently working on his Ph.D. degree in Computer Science at University of Houston. His research interests include fault tolerance, distributed computing, parallel computation and neural networks. He obtained his M.S. from University of Houston in 1988 and B.S. from Beijing University of Aeronautics and Astronautics in 1984, both in computer science.
Farokh B. Bastani received the B. Tech. degree in electrical engineering from the Indian Institute of Technology, Bombay, India, and the M.S. and Ph.D. degrees in electrical engineering and computer science from the University of California, Berkeley. He joined the University of Houston in 1980, where he is currently an Associate Professor of Computer Science. His research interests include software design and validation techniques, distributed systems, and fault-tolerant systems. He is a member of the ACM and the IEEE and is on the editorial board of theIEEE Transactions on Software Engineering. 相似文献
19.
Bi-XinLi Xiao-CongFan JunPang Jian-JunZhao 《计算机科学技术学报》2004,19(6):848-858
Program slicing can be effectively used to debug, test, analyze, understand and maintain objectoriented software. In this paper, a new slicing model is proposed to slice Java programs based on their inherent hierarchical feature. The main idea of hierarchical slicing is to slice programs in a stepwise way, from package level, to class level, method level, and finally up to statement level. The stepwise slicing algorithm and the related graph reachability algorithms are presented, the architecture of the Java program Analyzing TOol (JATO) based on hierarchical slicing model is provided, the applications and a small case study are also discussed. 相似文献
20.
SungJin Choi MaengSoon Baik JoonMin Gil SoonYoung Jung ChongSun Hwang 《Applied Intelligence》2006,25(2):199-221
Peer-to-peer grid computing is an attractive computing paradigm for high throughput applications. However, both volatility
due to the autonomy of volunteers (i.e., resource providers) and the heterogeneous properties of volunteers are challenging
problems in the scheduling procedure. Therefore, it is necessary to develop a scheduling mechanism that adapts to a dynamic
peer-to-peer grid computing environment. In this paper, we propose a Mobile Agent based Adaptive Group Scheduling Mechanism
(MAAGSM). The MAAGSM classifies and constructs volunteer groups to perform a scheduling mechanism according to the properties
of volunteers such as volunteer autonomy failures, volunteer availability, and volunteering service time. In addition, the
MAAGSM exploits a mobile agent technology to adaptively conduct various scheduling, fault tolerance, and replication algorithms
suitable for each volunteer group. Furthermore, we demonstrate that the MAAGSM improves performance by evaluating the scheduling
mechanism in Korea@Home.
SungJin Choi is a Ph.D. student in the Department of Computer Science and Engineering at Korea University. His research interests include
mobile agent, peer-to-peer computing, grid computing, and distributed systems.
Mr. Choi received a M.S. in computer science from Korea University. He is a student member of the IEEE.
MaengSoon Baik is a senior research member at the SAMSUNG SDS Research & Develop Center. His research interests include mobile agent, grid
computing, server virtualization, storage virtualization, and utility computing.
Dr. Baik received a Ph.D. in computer science from Korea University.
JoonMin Gil is a professor in the Department of Computer Science Education at Catholic University of Daegu, Korea. His recent research
interests include grid computing, distributed and parallel computing, Internet computing, P2P networks, and wireless networks.
Dr. Gil received his Ph.D. in computer science from Korea University. He is a member of the IEEE and the IEICE.
SoonYoung Jung is a professor in the Department of Computer Science Education at Korea University. His research interests include grid computing,
web-based education systems, database systems, knowledge management systems, and mobile computing.
Dr. Jung received his Ph.D. in computer science from Korea University.
ChongSun Hwang is a professor in the Department of Computer Science and Engineering at Korea University. His research interests include
distributed systems, distributed algorithms, and mobile computing.
Dr. Hwang received a Ph.D. in statistics and computer science from the University of Georgia. 相似文献