Faculty Profiles - FUNABIKI Nobuo

MISC - FUNABIKI Nobuo

Division display 541 - 560 of about 573 ／ All the affair displays >>

A Maximum Neural Network Algorithm for Stable Marriage Problems

TAJIMA Shigeto, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 96 ( 583 ) 295 - 302 1997.3

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

In this paper, we propose a maximum neural network algorithm for the stable marriage problem using the maximum neuron model. The goal of the stable marriage problem is to find N stable pairs of N men and N women under given preference lists. A pair becomes unstable when there is an unpaired couple of a man and a woman who prefer each other to their actual partners. The simulation results through randomly generated instances show that the performance of our maximum neural network surpasses the existing neural network using the binary neuron model in terms of the convergence properly and the solution quality.

A Proposal of the N-Parallel Computation Method of the Neural Network for N-Queens Problems

YOSHIO Hiroaki, BABA Takayuki, FUNABIKI Nobuo, NISHIKAWA Seishi

The Transactions of the Institute of Electronics,Information and Communication Engineers. A 80 ( 1 ) 205 - 212 1997.1

A study on a two-phase neural network algorithm for channel assignment in cellular radio networks

OKUTANI Noriko, FUNABIKI Nobuo, NISHIKAWA Seishi

Technical report of IEICE. SS 96 ( 490 ) 33 - 40 1997.1

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

This paper presents a two-phase neural network algorithm for the channel assignment problem in a cellular radio network. For a set of call requests, the goal of this NP-complete problem is to find a channel assignment, which does not only satisfy interference constraints between channels, but also minimizes the total number of frequency bands or channels. The proposed algorithm consists of two phases: 1) calls in most crowded cells are assigned channels by a heuristic method, and 2) calls in the other cells are assigned channels by a neural network. The performance is verified through eight benchmark problems, where our algorithm always finds the optimum or near-optimum solutions. The comparison of simulation results shows that the solution quality is better than the existing algorithms.

A gradual neural-network approach for frequency assignment in satellite communication systems

Nobuo Funabiki, Seishi Nishikawa

IEEE Transactions on Neural Networks 8 ( 6 ) 1359 - 1370 1997

Language：English

A novel neural-network approach called gradual neural network (GNN) is presented for a class of combinatorial optimization problems of requiring the constraint satisfaction and the goal function optimization simultaneously. The frequency assignment problem in the satellite communication system is efficiently solved by GNN as the typical problem of this class in this paper. The goal of this NP-complete problem is to minimize the cochannel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate the increasing demands. The GNN consists of N × M binary neurons for the N-carrier-M-segment system with the gradual expansion scheme of activated neurons. The binary neural network achieves the constrain satisfaction with the help of heuristic methods, whereas the gradual expansion scheme seeks the cost optimization. The capability of GNN is demonstrated through solving 15 instances in practical size systems, where GNN can find far better solutions than the existing algorithm. © 1997 IEEE.

DOI： 10.1109/72.641459

A Binary Neural Network Algorithm for the Graph Partitioning Problem

TAMAKI Yasuhiro, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 96 ( 430 ) 49 - 56 1996.12

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

In this paper, we present a neural network algorithm using binary neurons for a graph two-partitioning problem. For a given graph G(V, E), the goal of this NP-hard problem is to find a partition of vertices in V into two groups such that not only the sum of vertex-weights in each group is within the upper bound, but also the sum of edge-weights between groups is minimized. We formulate a new energy function and introduce a shaking term in the motion equation in order to improve the solution quality. We compare the performance of the neural network with two existing typical algorithms through simulations in unweighted and weighted random graphs. The results show that the neural network is comparable with existing algorithms for vertex-unweighted graphs in terms of the solution quality, and that it is much better for vertex-weighted graphs.

An Evaluation of Four Existing Algorithms and a New Neural Network Algorithm for Traveling Salesman Problems

SHIKATA Yasuhito, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 96 ( 430 ) 33 - 40 1996.12

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The traveling salesman problem is a well-known NP-hard combinatorial optimization problem. To solve the problem many researchers have developed algorithms. In this paper, first, we compare the features of 4 main algorithms. Second, we propose a new neural network algorithm whose energy function takes 0 when the neuron outputs represent a tour. At last, we compare their performance with 5 bench mark problems .The results show that It is found that a proposal algorithm is superior to trivial neural network but inferior to these algorisms.

A Neural Network Algorithm for the Minimum Maximal Matching Problem

UMETANI Shunji, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 96 ( 393 ) 17 - 24 1996.11

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

For a given graph G(V,E), a subset M of E is called a matching of G if no pair of edges in M is adjacent to each other. In this paper, we present a neural network parallel algorithm for the minimum maximal matching problem. This NP-complete problem requires to find a maximal matching composed of the least number of edges in G. The neural network consists of N × N binary neurons for the N-vertex graph problem. In order to improve the solution quality, we present a heuristic term into the motion equation for diagonal neurons which represent the exclusion of vertices from the matching. We verify the performance through simulations using random graph, where our neural network finds better solutions than the greedy algorithm and the simulated annealing.

"Winner-take-all" methods of Maximum neuron model

TAKENAKA Yoichi, FUNABIKI Nobuo, NISHIKAWA Seishi

Technical report of IEICE. SS 96 ( 347 ) 25 - 32 1996.11

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The maximum neuron model provides efficient neural network solutions for combinatorial optimization problems. In this "winner-take-all" model, one and only one neuron with the maximum input value is always fired in each group of neurons to satisfy the selection constrain. The maximum neuron model can not only reduce the searching space, but also save the computation load. In this paper, we propose two methods of selecting one neuron from two or more neurons which have same maximum input value, named "Least index method" and "Previous selection method". The simulation results show that the performance of the previous selection method performs better than the least index method generally.

A maximum neural network algorithm for route selection problems in multihop radio networks

BABA Takayuki, HIROAKI Yoshio, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 96 ( 331 ) 9 - 16 1996.10

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

In a multihop radio network, packets are transmitted from source nodes to destination nodes by activating several links between nodes. Each node can either send a packet to or receive a packet from at most one of its adjacent nodes simultaneously. In order to minimize the transmission time for given requests, the problems must be solved of selecting a transmission route for each request (the routing problem) and of finding a link activation schedule (the link activation problem). The routing problem is decomposed into two sub-problems; the candidate extraction problem and the route selection problem. In this paper, we propose a neural network algorithm using the maximum neuron model for the route selection problem. We verify the performance through simulations, where our algorithm finds better solutions in shorter time than the existing algorithms. We also prove the NP-hardness of this problem.

A Neural Network Algorithm for the Graph Partitioning Problem

TAMAKI Yasuhiro, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 96 ( 178 ) 99 - 106 1996.7

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The graph partitioning problem requires to partition the vertices of a given graph into several groups within the specified size so as to minimize the sum of the edge weights between groups. In this paper, we propose a neural network algorithm for the graph two-partitioning problem using the binary neuron model. We introduce the shaking term inthe motion equation in order to improve the solution quality. For the performance evaluation, we applied the proposed algorithm for random graphs to compare the running time and the solution quality with existing algorithms. As for solution quality, our algorithm is nearly equal to the KL algorithm, whereas as for the running time, our algorithm is much faster than the KL algorithm.

Maximum Neural Network Algorithms for N-Queen Problems

TAKENAKA Yoichi, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Theoretical foundations of Computing 95 ( 498 ) 77 - 84 1996.1

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

This paper presents maximum neural network algorithms for N-queen problems using the maximum neuron model. The maximum neuron model is proposed by Takefuji et al. in order to provide efficient neural network solutions for combinatorial optimization problems. In this model, one and only one neuron is always fired in each group of neurons, which can not only reduce the searching space drastically but also save the computation load. The simulation results show that the performance of our maximum neural network surpasses the existing neural network for the same problem. Particularly, the maximum neural network is shown to be much suitable for the semi-synchronous computation.

A Neural Network Parallel Algorithm for One-shot Scheduling Problems in Multicast Packet Switching Systems with the Windowed Service

BABA Takayuki, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Theoretical foundations of Computing 95 ( 498 ) 93 - 102 1996.1

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The multicast packet switching system with the windowed service can replicate a packet in each window and sent out the copies from different output ports simultaneously. In order to maximize the throughput, the problem must be solved in real time to find a switching configuration not only satisfying the constraints on the system, but also maximizing the number of copied packets under transmission demands. In this paper, we focus on the one-shot scheduling problem in the system where all copies of each packet must be sent simultaneously. First, we prove the NP-hardness of the problem. Then, we propose the neural network composed of W x N binary neurons for the N-input-port-W-window system. We verify the performance through simulations in up to 100-ports-3-window systems, where our neural network always finds near-optimum solutions within the constant number of iteration steps.

A Proposal of a Neural Network Parallel Algorithm for Stable Marriage Problems

TAJIMA Shigeto, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Theoretical foundations of Computing 95 ( 498 ) 85 - 92 1996.1

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The stable marriage problem requires to find N stable pairs of N men and N women under given preference lists. A pair is unstable when a man and a woman who are not partners prefer each other to their actual partners. In this paper, we propose a neural network parallel algorithm for the stable marriage problem. We verify the performance through simulations on the synchronous parallel computation.

A neural network model for multilayer topological via minimization in a switchbox

Nobuo Funabiki, Seishi Nishikawa

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 15 ( 8 ) 1012 - 1020 1996

Language：English

This paper presents a new approach using a neural network model for the multilayer topological via minimization problem in a switchbox. Our algorithm consists of three steps: 1) dividing multiterminal nets into two-terminal nets, 2) finding a layer-assignment of the twoterminal nets by a neural network model so as to minimize the number of unassigned nets, and 3) embedding one via for each imassigned net by Marek-Sadowska's algorithm. The neural network model is composed of N x M processing elements to assign N two-terminal nets in an M -layer switchbox. The performante of our algorithm is verified by 15 benchmark problems where it can find optimum or near-optimum solutions. In the two-layer Burstein's switchbox, our algorithm finds a 15-via solution while the best known solution requires 20 vias. © 1996 IEEE.

DOI： 10.1109/43.511580

Comparisons of energy-descent optimization algorithms for maximum clique problems

FUNABIKI N.

IEICE Trans. Fundamentals 79 ( 4 ) 452 - 460 1996

Language：English Publisher：The Institute of Electronics, Information and Communication Engineers

A clique of a graph G (V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time "energy-descent optimization" algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that "RaCLIQUE," the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.

Neural networks for the unicast problem and the multicast problem in the multicast packet switching system

BABA Takayuki, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 95 ( 405 ) 83 - 89 1995.12

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

With the packet replication, the multicast packet switching system with N input ports and N output ports can send n(≦N) copies of each packet to different output ports simultaneously. In order to maximize the throughput, the problem must be solved in real time to find a switching configuration not only satisfying the constraints on the system but also sending the maximum number of copied packets under transmission demands. In this paper, first, we focus on the unicast problem (n=1) in the multicast packet switching system and we solve by using the improved neural network. Then, we extend this idea to the multicast problem (n≧2) and we newly propose a neural network. We verified the performance through simulations, where our neural network can always find optimum solutions within constant number of iteration steps.

A study on the parallel computation of the neural network for N-Queen problems

YOSHIO Hiroaki, FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE technical report. Neurocomputing 95 ( 405 ) 75 - 82 1995.12

Language：Japanese Publisher：The Institute of Electronics, Information and Communication Engineers

The N-Queen problem has been studied by many researchers as the typical combinatorial optimization problem. In this paper, we first compared the performance of two existing neural networks both on the sequential computation and on the synchronous parallel computation. Then, we improved the parallel computation so as to avoid the degradation of the convergence rate. Finally, we proposed the asynchronous parallel computation which is suitable for a parallel machine with a maximum of N processors. We verified through simulations that the proposed method provides 100% convergence rate in up to 500-Queen problems.

"An improved neural network for channel assignment problems in cellular mobile communication systems,"

FUNABIKI Nobuo, NISHIKAWA Seishi

IEICE Transactions on Communications E78-B ( 8 ) 1187 - 1196 1995.8

Language：English Publisher：The Institute of Electronics, Information and Communication Engineers

This paper presents an improved neural network for channel assignment problems in cellular mobile communication systems in the new co-channel interference model. Sengoku et al. first proposed the neural network for the same problem, which can find solutions only in small size cellular systems with up to 40 cells in our simulations. For the practical use in the next generation's cellular systems, the performance of our improved neural network is verified by large size cellular systems with up to 500 cells. The newly defined energy function and the motion equation with two heuristics in our neural network achieve the goal of finding optimum or near-optimum solutions in a nearly constant time.

Neural Networks for Access Control in Multicast Packet Switching System

BABA Takayuki, FUNABIKI Nobuo, NISHIKAWA Seishi

Proceedings of the IEICE General Conference 75 - 75 1995

Neural Networks for The N-Queen problems

YOSHIO Hiroaki, FUNABIKI Nobuo, NISHIKAWA Seishi

Proceedings of the IEICE General Conference 17 17 - 17 1995

　 PREV - NEXT 　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29