Faits :
A.
Par jugement du 3 mars 2011, confirmé le 15 août 2011 par la Cour d'appel pénale du Tribunal cantonal vaudois, le Tribunal correctionnel de l'arrondissement de Lausanne a condamné X._, pour tentative de meurtre par dol éventuel, agression, lésions corporelles simples qualifiées et infraction à la Loi fédérale sur les étrangers (LEtr; RS 142.20), à une peine privative de liberté de sept ans, sous déduction de la détention subie avant jugement.
Outre cette condamnation, le casier judiciaire suisse de X._ mentionne une peine de six ans de réclusion, prononcée le 22 février 2005 pour vol, brigandage et dommages à la propriété. Par ailleurs, le 7 février 2014, il a été condamné à 120 jours-amende pour lésions corporelles simples et injure. Le casier judiciaire français du condamné fait état de cinq inscriptions dont une relative à une peine d'un an d'emprisonnement prononcée le 9 mai 1996 pour violence commise en réunion suivie d'incapacité supérieure à huit jours.
X._ a atteint les deux tiers de sa peine le 28 janvier 2015, la fin de celle-ci arrivant à échéance le 29 mai 2017.
B.
Par décision du 29 janvier 2016, le Collège des Juges d'application des peines a refusé la libération conditionnelle à X._ (I), a saisi le Tribunal correctionnel de l'arrondissement de Lausanne en vue de l'examen du prononcé d'une mesure thérapeutique institutionnelle ou d'un internement à l'endroit de X._ (II) et a laissé les frais de la décision à la charge de l'Etat (III).
C.
Par arrêt du 1 er mars 2016, la Chambre des recours pénale du Tribunal cantonal vaudois a rejeté le recours de X._, dans la mesure de sa recevabilité (I), a confirmé la décision du 29 janvier 2016 (II) et a ordonné la transmission de la cause au Tribunal correctionnel de l'arrondissement de Lausanne (III).
C.a. En substance, le refus de libération conditionnelle repose sur les rapports et avis suivants.
Les Etablissements pénitentiaires de la Plaine de l'Orbe (EPO), où était détenu X._, ont élaboré un plan d'exécution de peine (PES), avalisé le 16 août 2012 par l'Office d'exécution des peines (OEP). Il en ressort notamment que X._ s'est montré discret, courtois, autonome et peu demandeur au cellulaire. Il a refusé de participer à une démarche évaluative, déclarant ne pas être intéressé par une telle approche. Au chapitre des facteurs de risques, il est fait état de la violence dont X._ a fait preuve par le passé, son instabilité professionnelle, sa dépendance à l'alcool et au cannabis, l'échec antérieur de la surveillance (plusieurs sursis accordés ayant dû être révoqués) et le manque de soutien personnel. S'agissant des facteurs protecteurs, la gestion et l'autocontrôle de X._ dans le cadre des EPO sont mentionnés. Il ressort du document que X._ n'a entrepris aucune démarche en vue d'indemniser ses victimes. Au vu de son refus de collaborer à l'établissement de son PES, il a été renoncé à planifier d'éventuelles ouvertures de régime.
Dans son rapport du 8 août 2014, la direction des EPO a émis un préavis défavorable quant à une éventuelle libération conditionnelle et a précisé qu'aucun élargissement de régime ne paraissait envisageable en l'état.
La Commission interdisciplinaire consultative concernant les délinquants nécessitant une prise en charge psychiatrique (CIC) a rendu un avis le 20 novembre 2013 constatant l'état de dangerosité bien établi et visiblement préoccupant de X._ et préconisant la mise en oeuvre d'une expertise psychiatrique. Constatant que le précité avait refusé de se soumettre à l'expertise préconisée, la CIC a relevé, par avis du 14 octobre 2014, qu'au vu de la dangerosité élevée de X._, la perspective d'une fin de peine sans la moindre participation à son amendement, ni de moyens disponibles et utiles pour prévenir une très probable récidive, implique l'examen des possibilité de mise en place d'une mesure d'internement au sens de l'<ref-law>.
Par saisine du 16 septembre 2014, complétée par envoi du 7 novembre 2014, l'OEP a proposé au Collège des Juges d'application des peines de refuser l'élargissement anticipé de X._, invoquant notamment un pronostic défavorable quant à son comportement futur ainsi que sa dangerosité préoccupante.
Sur ordre de la Présidente du Collège des Juges d'application des peines du 27 avril 2015, un rapport d'expertise psychiatrique a été déposé le 1 er août 2015 par l'expert A._. Retenant un diagnostic de schizophrénie paranoïde, l'expert a relevé que dans un contexte carcéral, le risque de comportements violents du condamné devait être qualifié de faible à moyen, une décompensation psychotique aigüe ne paraissant guère probable, sauf événements contingents stressants. En revanche, l'expert a fait état d'un risque moyen à élevé de réitération d'actes violents hors du contexte institutionnel actuel. L'expert qualifie de " pertinente " l'hypothèse d'un traitement institutionnel, tout en relevant que cette mesure devrait être préparée dans la logique d'un travail à plusieurs et non pas introspectif.
Le 8 octobre 2015, le Ministère public a préavisé négativement l'octroi de la libération conditionnelle de X._ et a requis la saisine du Tribunal correctionnel en vue du prononcé d'une mesure.
C.b. Ensuite de menaces hétéro-agressives proférées à l'encontre de ses codétenus, X._ a été informé par l'OEP, le 20 juillet 2015, qu'il avait un délai de 5 jours pour s'opposer à son transfert dans un autre établissement d'exécution de peines et que l'absence de déterminations dans le délai imparti serait considérée comme un accord de sa part. Sans nouvelle, l'OEP a transféré X._, le 5 octobre 2015, aux Etablissements pénitentiaires de Pöschwies à Zurich.
D.
X._ forme un recours en matière pénale auprès du Tribunal fédéral contre la décision cantonale et conclut, avec suite de frais et dépens, principalement, à sa réforme en ce sens qu'il est renoncé à transmettre la cause au Tribunal d'arrondissement en vue de l'examen du prononcé d'une mesure et qu'il est libéré conditionnellement dès le moment où il pourra être remis aux autorités compétentes assurant son renvoi (<ref-law>). Subsidiairement, il conclut à l'annulation de la décision cantonale et au renvoi de la cause à la cour cantonale. Il requiert le bénéfice de l'assistance judiciaire et sollicite l'octroi de l'effet suspensif au recours.
Par ordonnance du 30 juin 2016, la demande d'effet suspensif a été rejetée.

Considérant en droit :
1.
Le recours en matière pénale est ouvert contre les décisions sur l'exécution de peines et de mesures (<ref-law>).
2.
Se fondant notamment sur les art. 3 al. 2 let. c CPP, 29 al. 2 Cst., 6 par. 3 CEDH et 14 par. 3 Pacte ONU II, le recourant invoque une violation de son droit d'être entendu dans la mesure où son audition en présence de l'expert psychiatrique lui a été refusée par les premiers juges après son transfert des EPO aux Etablissements pénitentiaires de Pöschwies à Zurich.
2.1. Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst., comprend notamment pour le justiciable le droit de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'obtenir l'administration des preuves pertinentes et valablement offertes, de participer à l'administration des preuves essentielles et de se déterminer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 6.3.1 p. 299).
Le droit d'être entendu n'empêche pas le juge de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de se forger une conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, il a la certitude qu'elles ne pourraient pas l'amener à modifier son opinion (<ref-ruling> consid. 5.3 p. 236). L'appréciation (anticipée) des preuves n'est revue par le Tribunal fédéral que sous l'angle restreint de l'arbitraire (cf. <ref-ruling> consid. 3 p. 157)
2.2. Selon la cour cantonale, c'est à juste titre que les premiers juges ont considéré qu'il n'y avait pas lieu d'entendre le recourant en présence de l'expert afin d'actualiser les conclusions de l'expertise après le changement de lieu de détention. Le rapport d'expertise avait été rendu très peu de temps avant la notification de la décision de première instance et il ne se justifiait pas de l'actualiser. Le fait nouveau que constitue le transfert était sans pertinence. Au demeurant, le pronostic en vue de la libération conditionnelle se fondait de manière générale sur toute la période de détention du condamné et non sur une période limitée. Partant, cette audition n'était pas de nature à modifier l'appréciation des premiers juges.
2.3. Le recourant n'est pas recevable à s'en prendre à la décision prise par les EPO de le transférer dans un autre pénitencier, dès lors qu'elle ne fait pas l'objet de la présente procédure (<ref-law>). Pour les mêmes motifs, c'est également en vain qu'il fonde son argumentation sur la base de décisions antérieures de refus de libération conditionnelle.
La majeure partie des arguments du recourant se concentre sur le fait que l'expertise ne se prononce pas sur ses nouvelles conditions de détention depuis le transfert. Ce faisant, il s'en prend en réalité à la valeur probante de l'expertise psychiatrique, faute d'actualité, et à son appréciation (cf. infra consid. 3.5).
Le recourant ne prétend pas avoir requis un complément d'expertise qui lui aurait été refusé. Il ne conteste pas avoir eu l'occasion de s'exprimer sur le contenu de l'expertise judiciaire déposée le 1er août 2015. Cela étant, l'on peine à comprendre en quoi consisterait la violation du droit d'être entendu qu'il invoque.
Le recourant échoue à démontrer dans quelle mesure le refus de l'auditionner une nouvelle fois après son transfert constituerait une appréciation anticipée arbitraire des preuves. En effet, se concentrant sur des passages de l'expertise psychiatrique, il n'indique d'aucune manière ce qu'une seconde audition pourrait révéler de pertinent pour l'issue de la cause, restreinte à la seule question de la libération conditionnelle. Dans ce cadre, la question de savoir si les conditions de détention postérieures au transfert correspondent aux recommandations de l'expert quant au traitement à prodiguer n'est pas pertinente. Cette question n'a d'importance qu'au regard de la procédure de changement de sanction (cf. <ref-law>), laquelle n'est pas l'objet de la présente cause.
3.
Le recourant reproche à la cour cantonale d'avoir violé l'<ref-law> en lui refusant sa libération conditionnelle. Selon lui, seuls les éléments négatifs du dossier ont été retenus, dans un processus inadmissible. Il fait valoir une appréciation arbitraire des preuves.
3.1. Aux termes de l'<ref-law>, l'autorité compétente libère conditionnellement le détenu qui a subi les deux tiers de sa peine, mais au moins trois mois de détention, si son comportement durant l'exécution de la peine ne s'y oppose pas et s'il n'y a pas lieu de craindre qu'il ne commette de nouveaux crimes ou de nouveaux délits. La libération conditionnelle constitue la dernière étape de l'exécution de la sanction pénale. Elle est la règle et son refus l'exception, dans la mesure où il n'est plus exigé qu'il soit à prévoir que le condamné se conduira bien en liberté (cf. art. 38 ch. 1 al. 1 aCP), mais seulement qu'il ne soit pas à craindre qu'il commette de nouveaux crimes ou délits. Autrement dit, il n'est plus nécessaire pour l'octroi de la libération conditionnelle qu'un pronostic favorable puisse être posé. Il suffit que le pronostic ne soit pas défavorable (<ref-ruling> consid. 2.2 p. 203 s.).
Le pronostic à émettre doit être posé sur la base d'une appréciation globale, prenant en considération les antécédents de l'intéressé, sa personnalité, son comportement en général et dans le cadre des délits qui sont à l'origine de sa condamnation, le degré de son éventuel amendement ainsi que les conditions dans lesquelles il est à prévoir qu'il vivra (<ref-ruling> consid. 2.3 p. 203 s. et les arrêts cités). La nature des délits commis par l'intéressé n'est, en tant que telle, pas à prendre en compte, en ce sens que la libération conditionnelle ne doit pas être exclue ou rendue plus difficile pour certains types d'infractions. Toutefois, les circonstances dans lesquelles l'auteur a encouru la sanction pénale sont également pertinentes dans la mesure où elles sont révélatrices de sa personnalité et donnent ainsi certaines indications sur son comportement probable en liberté. Au demeurant, pour déterminer si l'on peut courir le risque de récidive, inhérent à toute libération qu'elle soit conditionnelle ou définitive, il faut non seulement prendre en considération le degré de probabilité qu'une nouvelle infraction soit commise mais également l'importance du bien qui serait alors menacé. Ainsi, le risque de récidive que l'on peut admettre est moindre si l'auteur s'en est pris à la vie ou à l'intégrité corporelle de ses victimes que s'il a commis par exemple des infractions contre le patrimoine (<ref-ruling> consid. 2a p. 115 s.). Il résulte de ce qui précède qu'il ne suffit pas que le comportement adopté par le condamné pendant sa détention ne s'oppose pas à son élargissement (<ref-ruling> consid. 1a p. 7).
Dans l'émission du pronostic, l'autorité compétente dispose d'un large pouvoir d'appréciation. Le Tribunal fédéral n'intervient que si elle en a abusé, notamment lorsqu'elle a omis de tenir compte de critères pertinents et s'est fondée exclusivement sur les antécédents du condamné (<ref-ruling> consid. 2.3 p. 204).
3.2. Le Tribunal fédéral est lié par les constatations de fait de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, soit pour l'essentiel de façon arbitraire au sens de l'art. 9 Cst. Il n'entre pas en matière sur les critiques de nature appellatoire et n'examine la violation de droits fondamentaux que si ce moyen est invoqué et motivé par le recourant (<ref-law>), c'est-à-dire s'il a été expressément soulevé et exposé de manière claire et détaillée (<ref-ruling> consid. 1.3.1 p. 253).
En matière d'appréciation des preuves et d'établissement des faits, il y a arbitraire lorsque l'autorité ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision, lorsqu'elle se trompe manifestement sur son sens et sa portée, ou encore lorsque, en se fondant sur les éléments recueillis, elle en tire des constatations insoutenables (<ref-ruling> consid. 4.2 p. 234; <ref-ruling> consid. 4.2 p. 560).
3.3. La cour cantonale a posé un pronostic défavorable, notamment pour les motifs suivants.
Elle a relevé l'important passé judiciaire du recourant, précisant qu'à peine sorti de prison pour une condamnation de six ans pour brigandage, il a immédiatement été condamné à une peine privative de liberté de sept ans, notamment pour tentative de meurtre, agression et lésions corporelles simples. Elle s'est également fondée sur l'expertise psychiatrique qui faisait état d'un risque moyen à élevé de commettre de nouveaux passages à l'acte violents, hors du contexte institutionnel. Elle a considéré que les sanctions disciplinaires infligées au recourant pendant sa détention (le 14 août 2012 pour atteinte à l'intégrité physique; le 3 mars 2014 pour fraude et trafic; le 8 juillet 2015 pour atteinte à la liberté et atteinte à l'honneur et le 14 juillet 2015 pour atteinte à l'honneur) démontraient que ce dernier pouvait adopter un comportement violent même dans un cadre strict. S'agissant de ses projets futurs, le recourant n'avait présenté aucun plan concret, se bornant à expliquer qu'il souhaitait rentrer dans son pays d'origine et recommencer une nouvelle vie. Sur ce dernier point, la cour cantonale a retenu qu'il avait refusé de collaborer avec les autorités compétentes en vue de son éventuel refoulement. En outre, le recourant n'avait pas fait preuve de l'introspection et de l'amendement qu'on pouvait attendre de lui, dans la mesure où il avait déclaré en audience de première instance qu'il estimait sa peine un peu lourde et n'était pas totalement d'accord avec la version des faits retenue dans le jugement de condamnation. Il n'avait pas entrepris toutes les démarches possibles en vue du paiement des indemnités dues à ses victimes. La cour cantonale a pris en compte l'avis de la CIC qui parlait d'un état de dangerosité bien établi et visiblement préoccupant, à tel point qu'elle a préconisé le prononcé d'une mesure d'internement. Enfin, elle a retenu que tous les intervenants étaient unanimes pour dire que l'attitude actuelle du recourant faisait craindre un nouveau passage à l'acte.
3.4. Au vu de l'appréciation globale du pronostic du recourant, fondée sur les éléments pertinents et convergents précités, l'on ne saurait considérer que la cour cantonale aurait abusé de son large pouvoir d'appréciation. D'ailleurs, le recourant ne prétend pas qu'elle aurait omis de tenir compte de critères pertinents. Il se contente de critiquer l'appréciation cantonale s'agissant du risque de récidive, des réticences face aux démarches d'évaluation, de ses projets futurs et de son amendement.
3.5. S'agissant du risque de récidive, le recourant se livre à une interprétation personnelle, partant irrecevable de l'expertise psychiatrique pour tenter de nuancer le degré retenu par la cour cantonale (moyen à élevé) en fonction de ses conditions de détention. En tout état, il ressort expressément du rapport d'expertise que le risque de passage à l'acte varie selon que le recourant est dans un cadre carcéral ou hors de celui-ci (cf. expertise psychiatrique, p. 56). Aussi, le fait qu'il ait changé d'établissement pénitentiaire depuis le dépôt de l'expertise n'est pas apte à rendre insoutenable l'appréciation cantonale relative au risque de récidive. Sur ce point, sous couvert du grief relatif à son droit d'être entendu, le recourant échoue à démontrer dans quelle mesure l'expertise perdrait de sa pertinence au seul motif qu'elle a été déposée le 1er août 2015, antérieurement à son transfert d'établissement pénitentiaire.
En tout état, la cour cantonale s'est également fondée sur les comportements violents du recourant en prison et sur la dangerosité retenue par tous les intervenants à la procédure, pour conclure à un risque de récidive moyen à élevé en dehors d'un cadre carcéral.
Il n'y a pas lieu d'entrer en matière sur les explications personnelles du recourant portant sur les raisons de sa sanction disciplinaire du mois d'août 2012. Celles-ci sont purement appellatoires, partant irrecevables (art. 105 al. 2 et 97 al. 1 LTF).
3.6. Le recourant affirme de manière péremptoire que la cour cantonale n'aurait pas pris en considération son contexte personnel et ses faibles perspectives de resocialisation avant de retenir qu'il peinait à adhérer aux démarches d'évaluation proposées dans le cadre de sa détention. Cet argument se fonde sur une appréciation personnelle de la situation et est dès lors irrecevable. Le fait qu'il ait finalement participé à la mise en oeuvre d'une expertise psychiatrique ne rend pas insoutenable la constatation cantonale. En effet, tant le PES que la CIC font état de ses réticences quant aux démarches d'évaluation, (cf. arrêt entrepris, consid. B.c p. 3). Celles-ci ont d'ailleurs été verbalement réitérées devant le Juge de première instance (cf. arrêt entrepris, consid. B.e p. 4).
La cour cantonale a retenu que le recourant avait refusé de collaborer à son renvoi sur la base des informations transmises par le Service de la population (SPOP; cf. arrêt entrepris, consid. B.k p. 6). Les déclarations du recourant lors de son audition devant le Juge d'application des peines, selon lesquelles, il accepterait de collaborer avec le SPOP en vue de son renvoi uniquement à la condition qu'il obtienne sa libération conditionnelle (cf. PV d'audition du 11 décembre 2014, p. 4), ne sont pas aptes à mettre en doute les constatations cantonales. Il n'y a pas lieu d'entrer en matière sur les critiques purement appellatoires relatives aux démarches entreprises par l'Office fédéral des migrations pour le renvoi en Algérie.
3.7. La description que donne le recourant des aspects sociaux dont il pourrait bénéficier en Algérie est irrecevable. Elle ne permet en tout état pas de rendre insoutenable la constatation cantonale selon laquelle il ne présente pas de projet futur concret. Par ailleurs, le recourant se méprend lorsqu'il suggère que le refus de sa libération conditionnelle reposerait sur l'absence d'emploi ou de logement, compte tenu des nombreux éléments pris en compte par la cour cantonale.
3.8. La reformulation des déclarations faites devant le Juge d'application des peines relatives à l'introspection du recourant et à son amendement est purement appellatoire, partant irrecevable. En tant que le recourant admet trouver sa peine un peu lourde et avoir été négligent en ne réagissant pas à l'interruption de l'indemnisation des victimes, il ne fait que corroborer les constatations cantonales. Ce, quand bien même, il se serait déclaré d'accord de reprendre les versements.
3.9. En définitive, force est de constater que la cour cantonale a retenu un pronostic défavorable en procédant à une appréciation globale et dénuée d'arbitraire de très nombreux éléments pertinents et concordants. Compte tenu notamment du risque de récidive qualifié de moyen à élevé et de l'importance des biens qui seraient alors menacés (vie; intégrité corporelle), le raisonnement cantonal ne prête pas le flanc à la critique. Le seul pronostic défavorable suffit à justifier le refus de libérer conditionnellement le recourant au sens de l'<ref-law>.
4.
Le recourant s'en prend à la décision cantonale en tant qu'elle transmet son dossier au Tribunal correctionnel en vue de l'examen du prononcé d'une mesure ou d'un traitement institutionnel. Il fait valoir plusieurs griefs et en particulier une violation du principe " ne bis in idem ".
Le chiffre du dispositif cantonal qui ordonne la saisine du Tribunal correctionnel (III) constitue une décision préjudicielle ou incidente dans la mesure où elle ne met pas un terme définitif à la procédure d'examen d'un changement de sanction (sur la distinction entre une décision finale et incidente, cf. <ref-ruling> consid. 1 p. 568). Elle ne porte ni sur une demande de récusation ni sur la compétence (<ref-law>). Il n'apparaît pas et le recourant ne démontre pas que les conditions de l'<ref-law> seraient réalisées en l'espèce, en particulier s'agissant de la notification séparée (cf. <ref-ruling> consid. 1 p. 568). En tout état, il n'apparaît pas que la décision de transmettre le dossier en vue de l'ouverture d'une instruction causerait un préjudice irréparable au recourant (<ref-ruling> consid. 2.1 p. 204 s; cf. sur cette notion: <ref-ruling> consid. 3.1 p. 291), dès lors qu'il pourra faire valoir ses moyens de défense devant le juge du fond.
Par conséquent, le recours est irrecevable sur ce point.
5.
Le recours doit être rejeté dans la mesure où il est recevable. Comme les conclusions étaient vouées à l'échec, l'assistance judiciaire ne peut être accordée (<ref-law>). Le recourant, qui succombe, devra donc supporter les frais judiciaires (<ref-law>), dont le montant sera toutefois fixé en tenant compte de sa situation financière.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
La requête d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'600 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud, Chambre des recours pénale.
Lausanne, le 22 septembre 2016
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke