A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-01-22

AUTHORS

Vincenco Cutello , Maria Oliva , Mario Pavone , Rocco A. Scollo

ABSTRACT

In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (MWFVS) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem. More... »

PAGES

1-16

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1

DOI

http://dx.doi.org/10.1007/978-3-030-38629-0_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1124216802


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cutello", 
        "givenName": "Vincenco", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Oliva", 
        "givenName": "Maria", 
        "id": "sg:person.012340437717.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012340437717.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pavone", 
        "givenName": "Mario", 
        "id": "sg:person.07350620665.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07350620665.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Scollo", 
        "givenName": "Rocco A.", 
        "id": "sg:person.016661443761.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016661443761.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-01-22", 
    "datePublishedReg": "2020-01-22", 
    "description": "In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (MWFVS) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem.", 
    "editor": [
      {
        "familyName": "Matsatsinis", 
        "givenName": "Nikolaos F.", 
        "type": "Person"
      }, 
      {
        "familyName": "Marinakis", 
        "givenName": "Yannis", 
        "type": "Person"
      }, 
      {
        "familyName": "Pardalos", 
        "givenName": "Panos", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-38629-0_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-38628-3", 
        "978-3-030-38629-0"
      ], 
      "name": "Learning and Intelligent Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "challenging combinatorial optimization problems", 
      "Weighted Feedback Vertex Set Problem", 
      "tabu search metaheuristic", 
      "combinatorial optimization problems", 
      "local search procedure", 
      "clonal selection principle", 
      "real-life tasks", 
      "Feedback Vertex Set problem", 
      "search metaheuristic", 
      "tabu search", 
      "memetic algorithm", 
      "different algorithms", 
      "set problem", 
      "search procedure", 
      "different instances", 
      "genetic algorithm", 
      "best solution", 
      "algorithm", 
      "optimization problem", 
      "feedback vertex", 
      "hybrid IA", 
      "similar performance", 
      "immunological searches", 
      "instances", 
      "main strength characteristics", 
      "life tasks", 
      "selection principle", 
      "deterministic approach", 
      "metaheuristics", 
      "search", 
      "operators", 
      "task", 
      "robustness", 
      "efficiency", 
      "solution", 
      "applications", 
      "art", 
      "performance", 
      "vertices", 
      "reliability", 
      "advantages", 
      "order", 
      "experiments", 
      "principles", 
      "terms", 
      "field", 
      "purpose", 
      "results", 
      "state", 
      "characteristics", 
      "procedure", 
      "problem", 
      "approach", 
      "hypermutation", 
      "strength characteristics", 
      "aging", 
      "cloning", 
      "paper", 
      "Minimum Weighted Feedback Vertex Set (MWFVS) problem", 
      "Vertex Set (MWFVS) problem", 
      "MWFVS", 
      "operators of (i) cloning", 
      "iterative tabu search", 
      "MWFVS problem", 
      "Hybrid Immunological Search", 
      "Weighted Feedback Vertex"
    ], 
    "name": "A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem", 
    "pagination": "1-16", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1124216802"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-38629-0_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-38629-0_1", 
      "https://app.dimensions.ai/details/publication/pub.1124216802"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_449.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-38629-0_1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'


 

This table displays all metadata directly associated to this object as RDF triples.

156 TRIPLES      23 PREDICATES      91 URIs      84 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-38629-0_1 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N276999a33b9e4f669a3cfaf9c2807d07
4 schema:datePublished 2020-01-22
5 schema:datePublishedReg 2020-01-22
6 schema:description In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (MWFVS) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem.
7 schema:editor N899502f73c8c4e909f23f53c6a12c864
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb6b6b870896b4fc380a02a722e76159a
12 schema:keywords Feedback Vertex Set problem
13 Hybrid Immunological Search
14 MWFVS
15 MWFVS problem
16 Minimum Weighted Feedback Vertex Set (MWFVS) problem
17 Vertex Set (MWFVS) problem
18 Weighted Feedback Vertex
19 Weighted Feedback Vertex Set Problem
20 advantages
21 aging
22 algorithm
23 applications
24 approach
25 art
26 best solution
27 challenging combinatorial optimization problems
28 characteristics
29 clonal selection principle
30 cloning
31 combinatorial optimization problems
32 deterministic approach
33 different algorithms
34 different instances
35 efficiency
36 experiments
37 feedback vertex
38 field
39 genetic algorithm
40 hybrid IA
41 hypermutation
42 immunological searches
43 instances
44 iterative tabu search
45 life tasks
46 local search procedure
47 main strength characteristics
48 memetic algorithm
49 metaheuristics
50 operators
51 operators of (i) cloning
52 optimization problem
53 order
54 paper
55 performance
56 principles
57 problem
58 procedure
59 purpose
60 real-life tasks
61 reliability
62 results
63 robustness
64 search
65 search metaheuristic
66 search procedure
67 selection principle
68 set problem
69 similar performance
70 solution
71 state
72 strength characteristics
73 tabu search
74 tabu search metaheuristic
75 task
76 terms
77 vertices
78 schema:name A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem
79 schema:pagination 1-16
80 schema:productId N0d1bcc4759a94236ad7fb0691a76d1b1
81 N15d5a676f9ee4af4ba453c4a814cab63
82 schema:publisher N94b6ebd2b80f44069eb08dfa7715125b
83 schema:sameAs https://app.dimensions.ai/details/publication/pub.1124216802
84 https://doi.org/10.1007/978-3-030-38629-0_1
85 schema:sdDatePublished 2022-01-01T19:25
86 schema:sdLicense https://scigraph.springernature.com/explorer/license/
87 schema:sdPublisher N3dbd7766f9eb43e38726bed739c2abc0
88 schema:url https://doi.org/10.1007/978-3-030-38629-0_1
89 sgo:license sg:explorer/license/
90 sgo:sdDataset chapters
91 rdf:type schema:Chapter
92 N037a823369744d4fa902647399bd9229 rdf:first sg:person.012340437717.50
93 rdf:rest N43700c485edb4f9ab5ce5ecf7ba73a15
94 N0d1bcc4759a94236ad7fb0691a76d1b1 schema:name doi
95 schema:value 10.1007/978-3-030-38629-0_1
96 rdf:type schema:PropertyValue
97 N112b7dfcec6b47d0b5387cee5d4c5fe2 schema:familyName Matsatsinis
98 schema:givenName Nikolaos F.
99 rdf:type schema:Person
100 N15d5a676f9ee4af4ba453c4a814cab63 schema:name dimensions_id
101 schema:value pub.1124216802
102 rdf:type schema:PropertyValue
103 N276999a33b9e4f669a3cfaf9c2807d07 rdf:first Nc6a1f5da6e4c43dc81bef2f9a14da42a
104 rdf:rest N037a823369744d4fa902647399bd9229
105 N3dbd7766f9eb43e38726bed739c2abc0 schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
107 N43700c485edb4f9ab5ce5ecf7ba73a15 rdf:first sg:person.07350620665.82
108 rdf:rest N81851dcfe2fd46388190db94423cce54
109 N53beda6deaa3469387d2cbb76ab984b4 schema:familyName Marinakis
110 schema:givenName Yannis
111 rdf:type schema:Person
112 N6c42db9223c946459c704361c915a97c rdf:first N53beda6deaa3469387d2cbb76ab984b4
113 rdf:rest N71ccde45a7384617a8761d8b16a5c857
114 N71ccde45a7384617a8761d8b16a5c857 rdf:first Nfe35b0dc62834eeeb42cba809cc72e18
115 rdf:rest rdf:nil
116 N81851dcfe2fd46388190db94423cce54 rdf:first sg:person.016661443761.18
117 rdf:rest rdf:nil
118 N899502f73c8c4e909f23f53c6a12c864 rdf:first N112b7dfcec6b47d0b5387cee5d4c5fe2
119 rdf:rest N6c42db9223c946459c704361c915a97c
120 N94b6ebd2b80f44069eb08dfa7715125b schema:name Springer Nature
121 rdf:type schema:Organisation
122 Nb6b6b870896b4fc380a02a722e76159a schema:isbn 978-3-030-38628-3
123 978-3-030-38629-0
124 schema:name Learning and Intelligent Optimization
125 rdf:type schema:Book
126 Nc6a1f5da6e4c43dc81bef2f9a14da42a schema:affiliation grid-institutes:grid.8158.4
127 schema:familyName Cutello
128 schema:givenName Vincenco
129 rdf:type schema:Person
130 Nfe35b0dc62834eeeb42cba809cc72e18 schema:familyName Pardalos
131 schema:givenName Panos
132 rdf:type schema:Person
133 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
134 schema:name Information and Computing Sciences
135 rdf:type schema:DefinedTerm
136 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
137 schema:name Artificial Intelligence and Image Processing
138 rdf:type schema:DefinedTerm
139 sg:person.012340437717.50 schema:affiliation grid-institutes:grid.8158.4
140 schema:familyName Oliva
141 schema:givenName Maria
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012340437717.50
143 rdf:type schema:Person
144 sg:person.016661443761.18 schema:affiliation grid-institutes:grid.8158.4
145 schema:familyName Scollo
146 schema:givenName Rocco A.
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016661443761.18
148 rdf:type schema:Person
149 sg:person.07350620665.82 schema:affiliation grid-institutes:grid.8158.4
150 schema:familyName Pavone
151 schema:givenName Mario
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07350620665.82
153 rdf:type schema:Person
154 grid-institutes:grid.8158.4 schema:alternateName Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy
155 schema:name Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy
156 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...